Given a string, find the longest substring that is also a palondrom. One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is, LongestPalindromicSubStr(S) = LCS(S, reverse(S)). LCS can be solved by DP in O(n^2) time […]
Tag Archives: longest palindrom
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
Given a string. Find minimum number of insertion (or deletions) required to make it a palindrom. For example, S=”abacba” can be transformed into the longest palindrom P1=”abacaba” just by inserting 1 char. Observe that as long as mirror positions has the same character we have a potential palindrome between the mirror positions (inclusive). Note that, […]