Question

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

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

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

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;
	    }
	}

}

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

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

// 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:
        mlen = 0
        start = end = 0
        n = len(s)
        dp = [ [False] * n for i in range(n) ]

        for j in range(n):
            for i in range(j + 1):
                dp[i][j] = (i == j) or (s[i] == s[j] and j - i == 1) or (s[i] == s[j] and dp[i + 1][j - 1])
                if dp[i][j] is True and j - i + 1 > mlen:
                    mlen = j - i + 1
                    start = i
                    end = j

        return s[start: end + 1]

func longestPalindrome(s string) string {
	n := len(s)
	dp := make([][]bool, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
	}
	mx, start := 1, 0
	for j := 0; j < n; j++ {
		for i := 0; i <= j; i++ {
			if j-i < 2 {
				dp[i][j] = s[i] == s[j]
			} else {
				dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
			}
			if dp[i][j] && mx < j-i+1 {
				mx, start = j-i+1, i
			}
		}
	}
	return s[start : start+mx]
}

function longestPalindrome(s: string): string {
    const n = s.length;
    const isPass = (l: number, r: number) => {
        while (l < r) {
            if (s[l++] !== s[r--]) {
                return false;
            }
        }
        return true;
    };
    let res = s[0];
    for (let i = 0; i < n - 1; i++) {
        for (let j = n - 1; j > i; j--) {
            if (j - i < res.length) {
                break;
            }
            if (isPass(i, j)) {
                res = s.slice(i, j + 1);
            }
        }
    }
    return res;
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let maxLength = 0,
        left = 0,
        right = 0;
    for (let i = 0; i < s.length; i++) {
        let singleCharLength = getPalLenByCenterChar(s, i, i);
        let doubleCharLength = getPalLenByCenterChar(s, i, i + 1);
        let max = Math.max(singleCharLength, doubleCharLength);
        if (max > maxLength) {
            maxLength = max;
            left = i - parseInt((max - 1) / 2);
            right = i + parseInt(max / 2);
        }
    }
    return s.slice(left, right + 1);
};

function getPalLenByCenterChar(s, left, right) {
    // 中间值为两个字符，确保两个字符相等
    if (s[left] != s[right]) {
        return right - left; // 不相等返回为1个字符串
    }
    while (left > 0 && right < s.length - 1) {
        // 先加减再判断
        left--;
        right++;
        if (s[left] != s[right]) {
            return right - left - 1;
        }
    }
    return right - left + 1;
}

public class Solution{
    public string LongestPalindrome(string s) {
        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int mx = 1, start = 0;
        for (int j = 0; j < n; ++j)
        {
            for (int i = 0; i <= j; ++i)
            {
                if (j - i < 2)
                {
                    dp[i, j] = s[i] == s[j];
                }
                else
                {
                    dp[i, j] = dp[i + 1, j - 1] && s[i] == s[j];
                }
                if (dp[i, j] && mx < j - i + 1)
                {
                    mx = j - i + 1;
                    start = i;
                }
            }
        }
        return s.Substring(start, mx);
    }
}

import std/sequtils

proc longestPalindrome(s: string): string =
  let n: int = s.len()
  var
    dp = newSeqWith[bool](n, newSeqWith[bool](n, false))
    start: int = 0
    mx: int = 1

  for j in 0 ..< n:
    for i in 0 .. j:
      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 = i
        mx = j - i + 1

  result = s[start ..< start+mx]

# Driver Code
# echo(longestPalindrome("adbdaba"))

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let n = s.len();
        let s = s.as_bytes();
        let is_pass = |mut l, mut r| {
            while l < r {
                if s[l] != s[r] {
                    return false;
                }
                l += 1;
                r -= 1;
            }
            true
        };
        let mut res = &s[0..1];
        for i in 0..n - 1 {
            for j in (i + 1..n).rev() {
                if res.len() > j - i {
                    break;
                }
                if is_pass(i, j) {
                    res = &s[i..=j];
                }
            }
        }
        res.into_iter().map(|c| char::from(*c)).collect()
    }
}

5 - Longest Palindromic Substring

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions