Longest Palindromic Substring Part I

November 20, 2011 in dynamic programming, string

Given a string S, find the longest palindromic substring in S.


This interesting problem has been featured in the famous Greplin programming challenge, and is asked quite often in the interviews. Why? Because this problem can be attacked in so many ways. There are five different solutions that I am aware of. Are you up to the challenge?

Head over to Online Judge to solve it now! (you may submit either C++ or Java solution)

Hint:
First, make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions. For example, “aba” is a palindome, “abc” is not.

A common mistake:
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):

Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.

This seemed to work, let’s see some examples below.

For example,
S = “caba”, S’ = “abac”.
The longest common substring between S and S’ is “aba”, which is the answer.

Let’s try another example:
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us a O(N2) DP solution which uses O(N2) space (could be improved to use O(N) space). Please read more about Longest Common Substring here.

Brute force solution, O(N3):
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).

Since verifying each substring takes O(N) time, the run time complexity is O(N3).

Dynamic programming solution, O(N2) time and O(N2) space:
To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:

P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on… 

This gives us a run time complexity of O(N2) and uses O(N2) space to store the table.

Additional exercise:
Could you improve the above space complexity further and how?

A simpler approach, O(N2) time and O(1) space:
In fact, we could solve it in O(N2) time without any extra space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.

You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N2).

Further Thoughts:
Does an O(N) solution exist? You bet! However, it is not trivial and requires some very clever observation. The O(N) solution is explained in my next post.

» Continue reading Longest Palindromic Substring Part II.

VN:F [1.9.22_1171]
Rating: 4.8/5 (75 votes cast)
Longest Palindromic Substring Part I, 4.8 out of 5 based on 75 ratings

62 responses to Longest Palindromic Substring Part I

  1. I solved this problem at my blog.

    VA:F [1.9.22_1171]
    0
  2. I solved it on codereview. I tried for a functional version with better than quadratic performance, since the one-liners were all quadratic.

    http://codereview.stackexchange.com/questions/5241/more-functional-way-of-writing-this-palindrome-extractor/5260#5260

    I’m afraid mine was definitely not one-liner. :-) The first version was half the size of that, but code density was way too high.

    VA:F [1.9.22_1171]
    0
  3. I also write a O(n) algorithm as Programming Praxis metioned in his URL. Submit to online judge system.

    VN:F [1.9.22_1171]
    0
  4. What about reversing the original string and then finding the longest common substring of both?

    VA:F [1.9.22_1171]
    -8
  5. @vaibhav that would not work. The string “abaaacedfaaabaxyz” would output “abaa” which is not the desired result.

    VA:F [1.9.22_1171]
    +1
  6. VA:F [1.9.22_1171]
    -1
  7. I think that mine is linear.

    VA:F [1.9.22_1171]
    0
  8. Java version:

    VA:F [1.9.22_1171]
    0
    • VA:F [1.9.22_1171]
      0
  9. @durbin @wayne @rachel I just added syntax highlighting for your code. This is an experimental feature. Just FYI, you can syntax highlight using [lang]your code here…[/lang]. Replace lang with your favorite language, in this case, lang=java.

    VN:F [1.9.22_1171]
    0
    • Is a single char a palindrome? And I think there is a bug in your second solution. When there is a single char string input, the expandAroundCenter() will return s.substr(1, 0). Is that correct?

      VA:F [1.9.22_1171]
      0
      • Very good observation. I missed that completely.

        If you notice carefully however, the code still runs fine. In C++, for a single char string input, s.substr(1,0) returns an empty string. In general, for s with length of n, s.substr(n, k) will always return an empty string for k >= 0.
        http://www.cplusplus.com/reference/string/string/substr/

        However, my code is not written in a good way. Good code should reflect clearly its intentions. Even though it does work, it is highly misleading as it seem like it is out of bounds. Thanks, and I have refined the code.

        VN:F [1.9.22_1171]
        0
  10. In JAVA, O(n*n):

    public class Palindrome {

    public static void main(String[] args) throws IOException {
    int min=-1;
    String s,sub,rev;
    StringBuffer temp;
    ArrayList arr = new ArrayList();
    int len;

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println(“Enter a string”);
    s = br.readLine();

    if(s.length() == 0)
    System.out.println(“None”);

    len = s.length();

    for(int i = 0; i < len; i++)
    {
    for(int j = i; j <= len; j++)
    {
    sub = s.substring(i,j);
    if(sub.length() min){
    min=sub.length();
    arr.add(sub);
    }
    }
    }
    }
    System.out.println(“Substring with longest palindrome – “+arr.get((arr.size()-1)));
    }
    }

    VA:F [1.9.22_1171]
    0
  11. string longestPalindrome(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    // NO #include’s are required
    if (s.size() == 1) {
    return s;
    }
    string t = “”;
    for (int i = 1; i = 0 && (i + j + 1) t.size()) {
    t = r;
    }
    j = 0;
    while (s[i - 1 - j] == s[i + j] &&
    (i – 1 – j) >= 0 && (i + j) t.size()) {
    t = r;
    }
    }
    return t;
    }

    VA:F [1.9.22_1171]
    0
  12. I think there is a bug in your 2nd code again, Say when s = “abba” and i = 1 . I come to p2 expandString takes(s,1,2) and in the while loop l becomes -1 and r becomes 4
    So when returning the substring u return s.substr(-1+1,4-(-1+1)) = s.substr(0,4) which is out of bounds.

    VA:F [1.9.22_1171]
    0
  13. it should be while(l > 0 && r < n-1 && s[l] == s[r])

    VA:F [1.9.22_1171]
    0
    • If you do this you would not compare the two characters at the end for equality. This would miss out some palindromes.

      VN:F [1.9.22_1171]
      0
  14. and also return s.substr(l,r-l-1)

    VA:F [1.9.22_1171]
    0
  15. Thnx for clear explanation….

    VA:F [1.9.22_1171]
    0
  16. Thnx for succinct explanation….

    VA:F [1.9.22_1171]
    0
  17. Hey 1337c0d3r,
    Being a non-native English speaker i find one para little confusing ..could you please rephrase the below paragraph in simple English ..Thank you in advance…

    ” We could see that the longest common substring method fails when there exists this ……… ” till the end of that paragraph ..particularly what do you mean by this “a reversed copy of a non-palindromic substring in some other part of S”…

    VA:F [1.9.22_1171]
    0
  18. Hi, I think there is a bug in this method:

    string expandAroundCenter(string s, int c1, int c2) {

    // that’s what to added to make it correct. otherwise if you have
    //s=”bc”, c1=0 and c2=1, you won’t be able to get into the while
    //loop, but when you return, you are returning based on the
    //modified index.

    if(s[c1]!=s[c2]){
    return “”;
    }
    int l = c1, r = c2;
    int n = s.length();
    while (l >= 0 && r <= n-1 && s[l] == s[r]) {
    l–;
    r++;
    }
    return s.substr(l+1, r-l-1);
    }

    VN:F [1.9.22_1171]
    0
  19. Could you please explain this paragraph again? I really didn’t get it…

    To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

    VA:F [1.9.22_1171]
    0
  20. The DP method fails for your counterexample in the beginning of the article. Try “abartaba”

    VA:F [1.9.22_1171]
    0
  21. I can not understand the table[1000][1000]
    Why 1000? How did you come up with 1000?Could you please explain?

    VA:F [1.9.22_1171]
    0
  22. I have a solution and passed all the test cases, I used two for loops and a recursive function inside the second loop, does this mean this is O(N3) in time??But my space is O(1), I think. Here is my code:

    VN:F [1.9.22_1171]
    0
  23. java version, passed both small and large,
    running time is n^2 , O(1) space

    public String longestPalindrome(String s) {
    int frontIndex = 0;
    int backIndex = 0;
    for (int i = 1; i = 0 && front frontIndex – backIndex + 1) {
    frontIndex = front – 1;
    backIndex = back + 1;
    }
    }
    back = i – 1; front = i;
    if (front + 1 = 0 && front + 1 frontIndex – backIndex + 1) {
    backIndex = back + 1;
    frontIndex = front;
    }
    }
    }
    String str = s.substring(backIndex, frontIndex + 1);
    return str;
    }

    VN:F [1.9.22_1171]
    0
  24. public String longestPalindrome(String s) {
    int frontIndex = 0;
    int backIndex = 0;
    for (int i = 1; i = 0 && front frontIndex – backIndex + 1) {
    frontIndex = front – 1;
    backIndex = back + 1;
    }
    }
    back = i – 1; front = i;
    if (front + 1 = 0 && front + 1 frontIndex – backIndex + 1) {
    backIndex = back + 1;
    frontIndex = front;
    }
    }
    }
    String str = s.substring(backIndex, frontIndex + 1);
    return str;
    }

    VN:F [1.9.22_1171]
    0
  25. Hello:

    I am not able to get the following lines
    “You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters.” Here, I am not clear why there are 2N-1 centers. Can somebody explain with some example?

    VA:F [1.9.22_1171]
    0
  26. The total number of brute force strings are not nc2. You have mentioned in the brute force solution as total number of substrings are nc2 which is incorrect.

    VA:F [1.9.22_1171]
    0
    • I think they are

      nc1 + Sum ( i = 1 to n-1) (nci) / 2 + ncn

      where nci = n combination i

      VA:F [1.9.22_1171]
      0
  27. This is the shortest solution.
    bool isPalindrome(string s){

    int i=0;
    int len=s.length();
    while(i<len/2)
    {
    if(s[i]!=s[len-i-1)
    return false;
    }
    return true;
    }

    VN:F [1.9.22_1171]
    0
  28. This is the shortest solution.
    bool isPalindrome(string s){

    int i=0;
    int len=s.length();
    while(i<len/2)
    {
    if(s[i]!=s[len-i-1)
    return false;
    i++;
    }
    return true;
    }

    VN:F [1.9.22_1171]
    +2
  29. I think I can come up with a O(nlogn) solution, by binary searching the longest length and use Hashtable to check palindromic string mactching. Really curious to know how the O(n) works. Because as far as I know in wiki, the suffix tree method actually takes O(nlog^2n), because although traversing suffix tree is O(n) time, building suffix tree needs O(nlog^2 n).

    VN:F [1.9.22_1171]
    0
  30. int find_long_palindrome(char * str,int *maxlen,int * begin4max)
    {
    if(str==NULL)
    return -1;

    int len=strlen(str);
    if(len==0)
    return 1;

    int i=0;
    int j=len-1;
    int end = len-1;
    int curindex=0;

    printf(“curindex=%d,end=%d\r\n”,curindex,end);
    while( (end-curindex)>*maxlen )
    {
    i=curindex;
    j=end;
    printf(“curindex=%d\r\n”,curindex);
    while(1)
    {
    i=curindex;
    int beginj=j;
    while(icurindex && i>=j )
    {
    *begin4max=curindex;
    *maxlen=beginj-curindex+1;
    curindex++;
    break;
    }

    j–;

    if(i>=j)
    {
    curindex++;
    break;
    }
    }
    }
    return 1;
    }

    VN:F [1.9.22_1171]
    0
    • it should be like this:
      int find_long_palindrome(char * str,int *maxlen,int * begin4max)
      {
      if(str==NULL)
      return -1;

      int len=strlen(str);
      if(len==0)
      return 1;

      int i=0;
      int j=len-1;
      int end = len-1;
      int curindex=0;

      printf(“curindex=%d,end=%d\r\n”,curindex,end);
      while( (end-curindex)>*maxlen )
      {
      i=curindex;
      j=end;
      printf(“curindex=%d\r\n”,curindex);
      int beginj=j;
      while(1)
      {
      i=curindex;
      j=beginj;
      while(icurindex && i>=j )
      {
      int tmp_begin4max=curindex;
      int tmp_maxlen=beginj-curindex+1;

      if(tmp_maxlen>(*maxlen))
      {
      *begin4max=curindex;
      *maxlen=beginj-curindex+1;

      char *pstr13=(char *)malloc(sizeof(char) * (*maxlen+2));
      int realwritelen=_snprintf(pstr13,(*maxlen)+1,”%s”,str+(*begin4max));
      if(realwritelen>0)
      {
      pstr13[realwritelen]=”;
      }

      printf(“\r\n–writestris=[%s]—–maxlen=[%d],begin4max=[%d]-realwritelen=[%d]-\r\n”,pstr13,*maxlen,*begin4max,realwritelen);
      free(pstr13);
      pstr13=NULL;
      }

      curindex++;
      break;
      }

      //j=beginj-1;
      beginj–;

      if(i>=j)
      {
      curindex++;
      break;
      }
      }
      }
      return 1;
      }

      VN:F [1.9.22_1171]
      0
  31. public class LongestPallindrome {
    public static void main(String[] args) {
    String str = “abac”;
    String longestPal = “”;
    for (int i = 0; i longestPal.length())
    {
    longestPal = palinString;
    }
    }
    System.out.println(“Finally **” + longestPal);

    }

    static String isPalindome(String str, int mid) {
    boolean flag = true;
    boolean isStart = true;
    char[] string = str.toCharArray();
    int length = string.length – 1;
    int left = mid, right = mid;
    while (flag && left > 0 && right < length)
    {
    if (isStart && string[left] == string[right + 1])
    {
    left–;
    right = right + 2;
    } else if (isStart && string[left - 1] == string[right])
    {
    left = left – 2;
    right++;
    } else if (string[left] == string[right])
    {
    left–;
    right++;
    } else
    {
    flag = false;
    }
    isStart = false;
    }
    if (flag && (left < 0 || right == length))
    {
    return str.substring(left, right + 1);
    }
    return str.substring(left , right+1);
    }
    }

    VA:F [1.9.22_1171]
    0
  32. “To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.”

    This is wrong – for ABAXYZXABA – the longest common substring candidate will be ABAX and it will have expected indices – yet it’s not a palindrome. I don’t see how this can be resolved by reversing the string and looking for longest common substring.

    VA:F [1.9.22_1171]
    0
    • “To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.”

      Can you please explain this through code?

      VA:F [1.9.22_1171]
      0
    • Even I didnt understand the argument given in the post w.r.t using LCSubstring(string, reverse(string). But one way I see that we could make it work is if we check if the substring is a palindrome or not. This essentially makes it a n^3 solution, however. I would think that the idea of checking indices upon using LCS(string, reverse(string)) would also turn out to be O(n^3). Any clarification on this regard would be appreciated. [As it may improve the clarity in the original post]

      But otherwise, the other solution looks clearly explained to me.

      VA:F [1.9.22_1171]
      0
  33. The last line in the longestPalindromeDP method should be:
    return s.substr(longestBegin, longestBegin + maxLen);

    VA:F [1.9.22_1171]
    0
  34. Great post!

    I think you can add a check for empty string in the expandAroundCenter.

    Thanks!

    VA:F [1.9.22_1171]
    0
  35. thanks this has been helpful

    VN:F [1.9.22_1171]
    0
  36. Here is my O(N2) code:

    #include

    class Solution {
    public:
    string longestPalindrome(string s) {
    if (s.length() <= 1) return s;
    if (s.length() <= 2 && s[0] == s[1]) return s;

    int start, length;
    int maxStart = 0;
    int maxLength = 0;

    for (int idx=0; idx<s.length(); idx++) {
    int expandable = min(idx, (int)s.length()-idx-1);
    // Center at idx;
    for (int expand=1; expand maxLength) {
    maxStart = start;
    maxLength = length;
    }
    // Center between idx and idx + 1;
    expandable = min(idx, (int)s.length()-idx-2);
    for (int expand=0; expand maxLength) {
    maxStart = start;
    maxLength = length;
    }
    }

    return s.substr(maxStart, maxLength);
    }
    };

    VA:F [1.9.22_1171]
    0
  37. DP top down solution :

    #include
    #include
    #include

    using namespace std;

    bool isPalindromString(const char * inputStr, int start, int end, int** palindromFlagTable){
    if(start > end){
    return false;
    }
    if(start == end){
    palindromFlagTable[start][end] = 1;
    return true;
    }
    if(palindromFlagTable[start][end] == 1 || palindromFlagTable[start][end] == -1){
    return palindromFlagTable[start][end] == 1 ? true : false;
    }
    if(inputStr[start] != inputStr[end]){
    palindromFlagTable[start][end] = -1;
    return false;
    }
    if(end == start + 1){
    palindromFlagTable[start][end] = 1;
    return true;
    }
    bool ret = isPalindromString(inputStr, start + 1, end – 1, palindromFlagTable);
    if(ret){
    palindromFlagTable[start][end] = 1;
    }else{
    palindromFlagTable[start][end] = -1;
    }
    return ret;
    }

    int main(int argc, char* argv[]){

    string input = string(“aaaabcbaacxxcaaccaa”);

    const char* inputStr = input.c_str();
    int strLen = strlen(inputStr);
    int ** palindromFlagTable = new int*[strLen]();
    for(int i = 0; i < strLen; i++){
    palindromFlagTable[i] = new int[strLen]();
    }

    int maxLen = INT_MIN;
    int begin = INT_MIN;
    for(int i = 0; i i ; j –){
    if(isPalindromString(inputStr, i , j, palindromFlagTable)){
    if(j – i + 1 > maxLen){
    maxLen = j – i + 1;
    begin = i;
    }
    }
    }
    }

    if(maxLen > 0){
    printf(“max len is [%d], and begin is [%d] and the sub string is [%s]\n”, maxLen, begin, input.substr(begin, maxLen).c_str());
    }else{
    printf(“not found \n”);
    }

    for(int i = 0 ; i < strLen; i++){
    delete[] palindromFlagTable[i];
    }
    delete[] palindromFlagTable;

    }

    VN:F [1.9.22_1171]
    0
  38. the second method is very interesting and simple!

    VN:F [1.9.22_1171]
    0
  39. Python version:

    import argparse

    def extend_for_palindrome(string_input, index):
    if index == 0 or index == len(string_input) -1 :
    return string_input[0]
    else:
    span = 1
    while index – span >=0 and index + span len(max_palindrome) else max_palindrome
    return max_palindrome

    if __name__ == ‘__main__’:
    parser = argparse.ArgumentParser( description=’Find the longest palindrome’)
    parser.add_argument( ‘-s’, ‘–string’, help=’input string’)

    args = parser.parse_args()

    string_input = args.string

    print ‘String input:’, string_input

    print ‘Max Palindrome:’, longest_palindrome(string_input)

    VN:F [1.9.22_1171]
    +1
  40. Python version:

    Re-posted with “code” tag:

    VN:F [1.9.22_1171]
    0
    • Not sure why this function is missing after added code tag

      def longest_palindrome(string_input):
      max_palindrome = string_input[0]
      for i, char in enumerate(string_input):
      current_palindrome =extend_for_palindrome(string_input, i)
      #print i, current_palindrome
      max_palindrome = current_palindrome if len(current_palindrome) > len(max_palindrome) else max_palindrome
      return max_palindrome

      VN:F [1.9.22_1171]
      0
    • VN:F [1.9.22_1171]
      0
  41. your expand code doesnt for string “cabad”, it returns ab

    VA:F [1.9.22_1171]
    0
  42. Good Question, I have see this question first in this list and I was looking for solution, glad that I found a decent explanation here.

    VA:F [1.9.22_1171]
    0
  43. my method

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.