Longest Palindromic Substring Part I

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.9/5 (116 votes cast)
Longest Palindromic Substring Part I, 4.9 out of 5 based on 116 ratings

87 thoughts on “Longest Palindromic Substring Part I

  1. Praveen

    @vaibhav that would not work. The string “abaaacedfaaabaxyz” would output “abaa” which is not the desired result.

    VA:F [1.9.22_1171]
    0
  2. durbin

    VA:F [1.9.22_1171]
    0
  3. wayne

    I think that mine is linear.

    VA:F [1.9.22_1171]
    +2
  4. rachel

    Java version:

    VA:F [1.9.22_1171]
    +1
    1. rachel

      VA:F [1.9.22_1171]
      +1
  5. Profile photo of 1337c0d3r1337c0d3r Post author

    @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
    1. quasar

      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]
      +1
      1. Profile photo of 1337c0d3r1337c0d3r Post author

        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]
        +1
        1. garima

          Pls correct me if I am wrong here..

          If we enter single character, we are not going to enter in the for loop itself as length is 1 then and the loop condition
          i=0; i<n-1; i++
          restricts to enter.
          Then, how come expandAroundCenter() function is called?

          VA:F [1.9.22_1171]
          0
  6. Prongs

    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
  7. Pingback: Longest Palindromic Substring Part II | LeetCode

  8. Qi Li

    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
  9. Pingback: Palindrome Number | LeetCode

  10. Razor

    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
  11. Pingback: longest palindrom | laibinshi

  12. Pingback: Common palidromes | Tamihughson

  13. Naveen

    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
  14. Profile photo of Shundan XiaoShundan Xiao

    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
  15. Omar Mohammad Othman

    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
  16. Rohit

    The DP method fails for your counterexample in the beginning of the article. Try “abartaba”

    VA:F [1.9.22_1171]
    0
  17. reader

    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
  18. Profile photo of SherrySherry

    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
  19. Profile photo of grubbyfangrubbyfan

    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
  20. Profile photo of grubbyfangrubbyfan

    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
  21. Pingback: Longest Palindromic Subsequence | This is how Cheng grows up

  22. Ashwani Kumar

    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]
    +1
    1. Kevin Hsu

      I think the idea is that we don’t know if the palindrome we are looking for is even or odd in length. Consider the following 2 examples:

      s = “aba”
      In this case, we need to call expandAroundCenter(s, i, i) to be able to successfully find this palindrome.

      s = “abba”
      In this case however, if we use the same approach as above, we would examine “abb”, “bba” instead of “abba”. Thus, we need to call expandAroundCenter(s, i, i+1).

      In summary, since we don’t know if the length we are looking for is even or odd, we will check for both, and return the longest substring.

      VA:F [1.9.22_1171]
      +1
  23. Aks

    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
  24. Profile photo of Yitong ZhouYitong Zhou

    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
  25. Pingback: leetcode: Longest Palindromic Substring solution | 烟客旅人 sigmainfy

  26. Pingback: Longest Palindromic Substring Part | cloris1000

  27. Profile photo of jackyhoujackyhou

    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
    1. Profile photo of jackyhoujackyhou

      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
  28. marutikutre

    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
  29. Dan

    “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
    1. AAS

      “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
    2. GT

      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
  30. Pingback: leetcode总结无止境系列之动态规划及比较 – Crystal

  31. Ramgopal Tanikella

    The last line in the longestPalindromeDP method should be:
    return s.substr(longestBegin, longestBegin + maxLen);

    VA:F [1.9.22_1171]
    0
  32. Pingback: Finding longest palindrome in a string « ..MindWrite..

  33. vismaster

    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
  34. Profile photo of illuminatingilluminating

    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
  35. Profile photo of mengfengmengfeng

    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
  36. Profile photo of mengfengmengfeng

    Python version:

    Re-posted with “code” tag:

    VN:F [1.9.22_1171]
    0
    1. Profile photo of mengfengmengfeng

      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
    2. Profile photo of mengfengmengfeng

      VN:F [1.9.22_1171]
      0
  37. Pingback: LeetCode - Longest Palindromic Substring | Darren's Blog

  38. Krishna

    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
  39. Pingback: CodeNirvana: Palidromic Number | {.SMan.Soft.}

  40. Pingback: CodeNirvana: Palidromic Numbers | {.SMan.Soft.}

  41. Profile photo of Jintao XiaoJintao Xiao

    my method

    VN:F [1.9.22_1171]
    0
  42. Pingback: Longest Palindromic Substring [LeetCode 87] | CHazyhabiT

  43. Pingback: Longest Palindromic Substring | akajj

  44. Pingback: leetcode example | Multimedia Feedback Demo

  45. Pingback: Algorithms – Strings and Numbers » Tech Blog

  46. vinoth

    Thank you for the code. It really helped me. However, I found couple of issues with the code.
    1. The return statement in “return s.substr(l+1, r-l-1);” must be changed to “return s.substr(l+1, r);”
    2. String cannot be accessed by “s[l] == s[r]”, rather it must be s.charAt(l) == s.charAt(r)

    VA:F [1.9.22_1171]
    +2
  47. Profile photo of Sean JiangSean Jiang

    Here is my solution. I think its an elegant O(N) solution in Java. Would like to be reviewed by the judge if possible.

    VN:F [1.9.22_1171]
    0
  48. Profile photo of GaryZhuGaryZhu

    VN:F [1.9.22_1171]
    0
  49. Profile photo of GaryZhuGaryZhu

    VN:F [1.9.22_1171]
    0
  50. Pingback: Longest Palindromic Substring [LeetCode 87] - Uzumaki Kyuubi

  51. Pingback: Longest Palindromic Substring [LeetCode 5] - Uzumaki Kyuubi

Leave a Reply

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

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