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.:)
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.