Thursday, November 6, 2014

Facebook: Find the longest palindrome in a given string

Find the longest palindromic substring in a given string

Leetcode: http://buttercola.blogspot.com/2014/08/leetcode-longest-palindromic-substring.html

DP Solution:
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean palin[][] = new boolean[n][n];
        
        String result = "";
        int maxLen = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2)||
                    (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1] == true)) {
                        palin[i][j] = true;
                        if (j - i + 1 > maxLen) {
                            result = s.substring(i, j + 1);
                            maxLen = j - i + 1;
                        }
                }
            }
        }
        
        return result;
    }
}

Discussion:
Time complexity: O(n^2).
Space complexity O(n^2).

A constant space solution:
We can even develop a O(1) space solution. For a string is palindrome, it must be mirrored across a central point. Here we must consider both the even and odd length of the string. For a string with odd length, e.g. aa, it is palindromic for s[lo] == s[hi] where lo = 0, and hi = 1. For odd length, e.g. aba, lo = 0, and hi = 2. So we can iterate the string and check its left and right points to see if it is mirrored.
Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) return s;
         
        int start = 0;
        String longestSub = "";
        int maxLen = 0;
         
        for (int i = 1; i < len; i++) {
            //check the longest palindromic substring with even length;
            int lo = i - 1;
            int hi = i;
             
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
             
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
             
            // check the longest palindromic substring with odd length
            lo = i - 1;
            hi = i + 1;
             
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
             
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
        }
        return s.substring(start, start + maxLen);
    }
}

No comments:

Post a Comment