(Longest Palindromic Substring)

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        for(int len = s.length(); len > 0; --len) {
            for(int j = 0; j <= s.length() - len; ++j) {
                String sub = s.substring(j, j + len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return new String();
    }
    
    private boolean isPalindrome(String s) {
        if(s.length() <= 1)
            return true;
        else
            return s.charAt(0) == s.charAt(s.length()-1) && 
                isPalindrome(s.substring(1,s.length()-1));
    }
}

Code (C++):

class Solution {
public:
    string longestPalindrome(string s) {
        for(int len = s.size(); len > 0; --len) {
            for(int i = 0; i <= s.size() - len; ++i) {
                string sub = s.substr(i, len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(string s) {
        if(s.size() <= 1)
            return true;
        else
            return s[0] == s[s.size() - 1] && 
            isPalindrome(s.substr(1,s.size()-2));
    }
};
Advertisements

5 Comments (+add yours?)

  1. aroudakili
    Mar 13, 2013 @ 15:57:43

    I think line 5 (Java) must be :
    String sub = s.substring(j, len);

    Reply

    • Runhe Tian
      Mar 13, 2013 @ 16:03:47

      No, the signature of substring method for String class is:
      substring(int beginIndex, int endIndex)
      I’m extracting a substring that starts at j and ends at j + len, with a total length of “len”. Is that clear?

      Reply

  2. asdas
    Jul 19, 2013 @ 00:56:43

    gr8 solution

    Reply

  3. Qwerty
    Jan 24, 2014 @ 22:08:30

    Have you tried running this code? j + len gives String index out of bounds.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: