FullOfDoubts's blog

By FullOfDoubts, history, 4 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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