Longest Palindromic Substring

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.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution1. DP O(n^2)

定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.

首先找个例子,比如S=”abccb”,
S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
………………….
由此就可以推导出规律

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

实现如下:

public String longestPalindrome(String s) {
    if (s == null) {
        return "";
    }
    String res = "";
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i - j <= 2) {
                dp[j][i] = s.charAt(i) == s.charAt(j);
            } else {
                dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
            }
            if (dp[j][i]) {
                if (i - j + 1 > res.length()) {
                    res = s.substring(j, i + 1);
                }
            }
        }
    }
    return res;
}

Solution2: Check both aba and abba 2 cases. O(n^2)

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    String result = "";

    //1. if it is like 'aba'
    for (int i = 0; i < s.length(); i++) {
        int count = 0;
        while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) {
            count++;
        }
        String palindrome = s.substring(i - count + 1, i + count);
        if (palindrome.length() > result.length()) {
            result = palindrome;
        }
    }

    //2. if it is like 'abba', the pivot would be the interval between i and i+1
    for (int i = 0; i < s.length() - 1; i++) {
        int count = 1;
        while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) {
            count++;
        }
        if (count > 1) {
            String palindrome = s.substring(i - count + 2, i + count);
            if (palindrome.length() > result.length()) {
                result = palindrome;
            }
        }
    }

    return result;
}

 

FacebookTwitterGoogle+Share

Maximum Product Subarray

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int maxProduct = Integer.MIN_VALUE;
    int preMax = 1;
    int preMin = 1;
    for (int i = 0; i < nums.length; i++) {
        int max, min;
        if (nums[i] >= 0) {
            max = Math.max(preMax * nums[i], nums[i]);
            min = Math.min(preMin * nums[i], nums[i]);
        } else {
            max = Math.max(preMin * nums[i], nums[i]);
            min = Math.min(preMax * nums[i], nums[i]);
        }
        maxProduct = Math.max(maxProduct, max);
        preMax = max;
        preMin = min;
    }
    return maxProduct;
}