Question

Formatted question description: https://leetcode.ca/all/5.html

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,
 * and there exists one unique longest palindromic substring.
 *
 * A palindrome is a word, phrase, number, or other sequence of characters
 * which reads the same backward or forward
 *
    Example 1:

    Input: "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.

    Example 2:

    Input: "cbbd"
    Output: "bb"

@tag-string
@tag-dp

Algorithm

First, let’s define what a palindrome is: a string that reads the same from front to back, such as “bob”, “level”, “noon”, and so on.

The longest palindrome substring is the longest palindrome substring within a string. There are five palindrome-related questions on LeetCode. Apart from this one, the other four are Palindrome Number, Validate Palindrome, Palindrome Partitioning, and Palindrome Partitioning II. The traditional method of verifying a palindrome is to check it two by two. We check the string symmetrically, and if it is equal, then for the problem of retrieving the palindrome substring, we need to treat each character as the center and find the palindrome string by expanding on both sides like a two-sided diffusion. This algorithm has a time complexity of O(n*n) and can be solved on OJ.

It is important to pay attention to the odd and even situations, because the length of the palindrome substring can be odd or even. For example, “bob” is an odd-form palindrome, and “noon” is an even-form palindrome. We should search for both forms of palindrome. For odd-length palindromes, we start from the current position as the center and expand to both sides. For even-length palindromes, we treat the current position and the next position as the middle two characters of the even-length palindrome, and then search on both sides.

Code

Java

public class Longest_Palindromic_Substring {

    // dynamic programming, note to avoid expensive operation
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }

        int longest = Integer.MIN_VALUE;
        int start = 0;
        int end = 0;

        // initialization， default all false
        // dp[i][j] meaning substring i-j is palindromic
        boolean[][] dp = new boolean[s.length()][s.length()];

        for(int i = 0; i < s.length(); i++) {

        	// @note: for the second pointer j, direction not important, same result
            // for(int j = i; j >= 0; j--) {
            for(int j = 0; j <= i; j++) {

                if(i == j || (s.charAt(i) == s.charAt(j) && i - j < 2) || (s.charAt(i) == s.charAt(j) && dp[i - 1][j + 1])) {
                    dp[i][j] = true;

                    // check max
                    if(i - j + 1 > longest) {
                        // @note: below is expensive, over time
                        // result = s.substring(j, i + 1);
                        longest = i - j + 1;
                        start = j;
                        end = i;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }


	// brute force, overtime
	public class Solution2 {
	    public String longestPalindrome(String s) {
	        if(s == null || s.length() == 0) {
	            return "";
	        }

	        String result = "";

	        for(int i = 0; i < s.length(); i++) {
	            for(int j = i + 1; j < s.length(); j++) {
	                String sub = s.substring(i, j + 1);
	                if(isPal(sub) && sub.length() > result.length()) {
	                    result = sub;
	                }
	            }
	        }

	        return result;
	    }

	    public boolean isPal(String s) {
	        char[] array = s.toCharArray();
	        int i = 0;
	        int j = array.length -1;

	        while(i <= j) {
	            if (array[i] != array[j]) {
	                return false;
	            }
	            i++;
	            j--;
	        }

	        return true;
	    }
	}

}

// OJ: https://leetcode.com/problems/longest-palindromic-substring/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    string longestPalindrome(string s) {
        int N = s.size(), start = 0, len = 0;
        bool dp[1001][1001] = {};
        for (int i = N - 1; i >= 0; --i) {
            for (int j = i; j < N; ++j) {
                if (i == j) dp[i][j] = true;
                else dp[i][j] = s[i] == s[j] && (i + 1 > j - 1 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > len) {
                    start = i;
                    len = j - i + 1;
                }
            }
        }
        return s.substr(start, len);
    }
};

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        start, mx = 0, 1
        for j in range(n):
            for i in range(j + 1):
                if j - i < 2:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
                if dp[i][j] and mx < j - i + 1:
                    start, mx = i, j - i + 1
        return s[start : start + mx]

############

class Solution(object):
  def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    left = right = 0
    n = len(s)
    for i in range(n - 1):
      if 2 * (n - i) + 1 < right - left + 1:
        break
      l = r = i
      while l >= 0 and r < n and s[l] == s[r]:
        l -= 1
        r += 1
      if r - l - 2 > right - left:
        left = l + 1
        right = r - 1
      l = i
      r = i + 1
      while l >= 0 and r < n and s[l] == s[r]:
        l -= 1
        r += 1
      if r - l - 2 > right - left:
        left = l + 1
        right = r - 1
    return s[left:right + 1]


class Solution:
	def longestPalindrome(self, s: str) -> str:
		dp = [[False for _ in range(len(s))] for _ in range(len(s))]
		ans = 0
		start = end = -1

        # please note: j is always smaller than i, ===> j < i
		for i, c1 in enumerate(s):
			for j, c2 in enumerate(s[:i + 1]):
				if i == j or (c1 == c2 and abs(i - j) < 2) or (c1 == c2 and dp[i - 1][j + 1]):
					dp[i][j] = True
					if i - j + 1 > ans:
						start = j
						end = i
						ans = max(ans, i - j + 1)
		return s[start: end + 1]

5 - Longest Palindromic Substring

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions