Hz_'s blog

How to solve this string problem?
By Hz_, history, 4 years ago, In English

Problem link

Problem statement
INPUT and OUTPUT format
SAMPLE

I don't understand why my code is getting wrong?

My approach to making the string non-decreasing as much as possible.

Can anyone please help me to fix my code for this problem or tell me a good approach to solve this problem?

*Now the submit option for this problem is disabled. It will be better if someone comes up with proof of his/her solution.:)

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

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you can do $$$dp[i][ch]$$$, denoting whether it is possible to sort the string upto $$$i^{th}$$$ character with the last character is $$$ch$$$.

The transition is simple, the interesting part is that for the current character you have to find all the character you can change it into, which I reckon from the problem statement will have a path from initial character to final character going by some edges, in the given graph of alphabets.

This is although not difficult to do. Naively, you start a search algorithm from any node, and find all the vertices reachable from it.

→ Reply