Link to the problem: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=466&page=show_problem&problem=4183

Problem Statement(abridged):

There are 2 strings **A** and **B** each of length **N**. Both consist of lowercase English letters. We want to convert string **A** into string **B**. In one move, we can choose any substring of **A**, and a character **ch**, ('a'<= **ch** <='z') and replace every character in the chosen substring with the chosen character **ch**. Compute the minimum number of moves required to convert **A** into **B**.

1<= **N** <=100

**Sample Input:**

zzzzzfzzzzz

abcdefedcba

abababababab

cdcdcdcdcdcd

**Sample Output:**

6

7

This looks like an range dp problem, wherein we define the subproblem for every substring and then combine those substrings optimally,(dp[i][j] is a function of dp[i][k] and dp[k][j]) but I can't come up with states or transitions, or any other meaningful observation.

Any hints/solutions would be appreciated.

Edit: Bumping this up, any ideas, need some help from the community as I practice alone :(

Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).