In http://www.spoj.com/problems/IOIPALIN/ problem why ans=n-lcs work please explain.
Do you still have this doubt or you worked it out using few examples?
After you’re reversing a string and then finding a LCS, if LCS > 1, it’s sure that you don’t need to add those characters anymore because they are / will be present on both the sides of the string after you make them palindrome. You just need to add the character which are not in the LCS in between the characters.
For example:
abcb
bcba
what’s the LCS?
bb
So you don’t need to add any more 'b’s. c and a is the only remaining characters, so you need to add those.
if LCS = 1, For example,
abcd
dcba
You need to add 3 characters and the other one will be in the middle. So the solution can be, abcdcba / dabcbad etc.
Lastly, why’re we even finding out LCS? Think of this greedily. What is the best way to make a palindrome? Adding as little characters as possible / Not adding as many characters as possible. And that is what LCS finds out.
3 Likes
the lcs subsequence is the common subsequence in both the forward string as well as the reversed string so no matter what u do u have to add the remaining characters in the reversed string so the minimum value of characters added should be at least the count of characters remaining ,i.e, those that do not contribute to lcs.
As far as the lcs is considered its common in both the strings so they do not pose much of a problem.