We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Longest Palindromic Subsequence
You are viewing a single comment's thread. Return to all comments →
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.