Find the longest palindrome of a String [Amazon,Microsoft]


Find the length and/or string of the longest palindrome of a string.

The problem appeared as an Interview question in Amazon, Microsoft.


One important property of a palindrome is if we remove the first and last characters of it , it would be another palindrome.

So A string S[a..b] will be a palindrome if and only if S[(a+1)…(b-1)] is a palindrome.

We can use DP to solve the problem.

  • Keep a 2D array of ARRAY [String.SIZE]  [String.SIZE] for keeping the length of palindrome found from the string.
  • Each char of the string is 1 length palindrome sub string. So ARRAY[i][i] = 1 , here i=0….String.SIZE
  • Now find the length of possible palindrome for  2 char length strings starting from each index of the string S.
  • similarly find palindrome for 3,4,…..char length string of the provided String S.

Problem Link


Comments are closed.