Longest Palindromic Substring

LeetCode Q 5 - 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.

Example 1:
Input: "babad" ; Output: "bab"
Note: “aba” is also a valid answer.
Example 2:
Input: "cbbd" ; Output: "bb"

Solution

Solution 1: Center Expanding

Time Complexity: O(n^2)
Space Complexity: O(1)

private int maxLen;
private int pos;
public String longestPalindrome(String s) {
	if (s == null || s.length() == 0) return "";

	for (int i = 0; i < s.length(); i++) {
		centerExpanding(s, i, i);
		centerExpanding(s, i, i + 1);
	}

	return s.substring(pos, pos + maxLen);
}

private void centerExpanding(String s, int left, int right) {
	while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
		left--; right++;
	}
	if (maxLen < right - left - 1) {
		pos = left + 1;
		maxLen = right - left - 1;
	}
}

Solution 2: DP

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1. Base Case:
   dp[i][i] = T ; dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1)
2. State Transfer Function:
   dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)

public String longestPalindrome(String s) {
	if (s == null || s.length() == 0) return "";
	
	boolean[][] dp = new boolean[s.length()][s.length()];
	int maxLen = 0, pos = 0;
	for (int i = 0; i < s.length(); i++) {
		for (int j = 0; j <= i; j++) {
			if (s.charAt(i) == s.charAt(j) && ((i - j) <= 2 || dp[j + 1][i - 1])) {
				dp[j][i] = true;
			}
			if(dp[j][i] && maxLen < i - j + 1) {
				maxLen = i - j + 1;
				pos = j;
			}
		}
	}
}