Sort 6 Discussions, By:
Please Login in order to post a comment
I can't believe I spent more than a day on this problem which is WRONG in every possible way.
For starters, the original testcase is wrong. For the string "aba" and k = 0, there are only 56 ways to insert a new character such that the length of the LPS remains 3.
Then, the problem solution assumes that there is no way to increase the length of the LPS more than 2 by adding only one character, which is obviously false.
For example, take string "abcdba", which has length 6 and LPS length 1.
You can turn the entire string into a palindrome by adding a "c" : "abcdcba" -> length of the LPS becomes 7.
Even if we are to interpret the problem definition by saying that you are only to extend the initially found LPS, it still wouldn't be correct for the original testcase.
How does "aba" have 104 possible combinations, It have only 58 combinations with palindrom length greater than or equal to 3
How can we decrease the time complexity? I'm getting time out in most of the test cases.
For the input aba and the value k = 0, the output is 104.
Could anyone explain how?
Thanks in advance
Best solution for C/C++ Java and Python. Check it now ~!