Longest Palindrome String

This question is quite interesting.

The first method you can comeup with is check every substring, which will take O(n^3) time.

Can we do better? We know that one character is a palindrome itself, we also know that if S[i+1][j-1] is a palindrome and S[i] == S[j], S[i][j] is a palindrome. In this way, we can build up a boolean array dp[i][j] to record if S[i][j] is a palindrome. dp[i][j] = dp[i+1][j-1] && s[i] == s[j].

initilzation, dp[i][i] = true, one char is always a palindrome.
fill up the matrix, this is a little bit tricky because we need dp[i+1][j-1], so outter loop i should start from the largest possible s.length()-2, while inner loop j should start from i to s.length() – 1. Also if j-i == 1 which means two adjacent char, then dp[i][j] = s[i] == s[j]. The code however is quite short:

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0)
            return "";
        boolean [][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++)
            dp[i][i] = true; // one char is a palindrome
        int max = 1;
        String r = new String() + s.charAt(0);
        for (int i = s.length() -2; i >= 0; i--) {
            for (int j = i+1; j < s.length(); j++) {
                if ((j-i) == 1) // if two adjacent char, just check if they are the same.
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                else
                    dp[i][j] = (s.charAt(i) == s.charAt(j))? dp[i+1][j-1] : false;
                if (dp[i][j] && j-i+1 > max) {
                    max = j-i+1;
                    r = s.substring(i, j+1);
                }
            }
        }
        return r;
    }
}

The above dp algorithm gives O(n^2) run time and O(n^2) space. But think about it, the dp is just starting from one char and extending it to both size. So we can simply scan through every char in the input string, and search to left and right for each character see if we can find a palindrome. This only takes O(1) space, and the same O(n^2) time.

You can also use the length of the string and the starting char instead of the start and end of the string, which might be more intuitive to come out

public class Solution {
    public String longestPalindrome(String s) {
        boolean [][] dp = new boolean [s.length()+1][s.length()];
        //int i = 1; size of the string we are checking
        //int j = 0; start index of the current string
        int max = 1;
        String res = String.valueOf(s.charAt(0));
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= s.length() - i; j++) {
                if (i == 1)
                    dp[i][j] = true; //one char is always palindrome
                else if ( i == 2)
                    dp[i][j] = s.charAt(j) == s.charAt(j+1);
                else
                    dp[i][j] = dp[i-2][j+1] && s.charAt(j) == s.charAt(j+i-1);
                if (dp[i][j] && i > max) {
                    max = i;
                    res = s.substring(j, j + i);
                }
            }
        }
        return res;
    }
}

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