Longest palindrome sub-string problem is famous for software programmers specially for interview purpose. you can be questioned to write a function that returns the longest palindrome in a given string. A palindrome is a sequence which reads the same backward or forward. For example “asantaatnasa” is sequence of character which reads same in backward or forward. in simple term if we reverse the sequence we will get same sequence.

lps

Longest palindrome sub-string problem: For example, the longest palindromic sub-string of “bananas” is “anana” and length is 5.

Simple solution with O(N²) time complexity

  • The give string is “bananas“. 
  • if we reverse the given sequence then we will get “sananab“.
  • Then our problem is to find longest common sub-string between these two strings “bananas”  and sananab“.
  • The longest common sub-string problem can be solved by recursive function with memoization with O(m*n) time complexity discussed in the article http://wikistack.com/longest-common-substring-problem/
  • Hence Longest common sub-string solution can be used to compute  Longest palindrome sub-string problem with  O(m*n) time complexity.

 Here is c code for Longest common sub-string solution with O(m*n) time complexity.