FullOfDoubts's blog

By FullOfDoubts, history, 4 weeks ago,

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

• +1

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by FullOfDoubts (previous revision, new revision, compare).