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
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 :(