0005. Longest Palindromic Substring

5. Longest Palindromic Substring #

Problem #

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

Problem Summary #

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

Solution Ideas #

  • This problem is very classic and has multiple solutions.

  • Solution 1: dynamic programming. Define dp[i][j] to represent whether the substring from the i-th character to the j-th character of the string is a palindrome. From the properties of palindromes, we know that after removing the same character from both ends of a palindrome, the remaining substring is still a palindrome. Therefore, the state transition equation is dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1]). Pay attention to special cases: when j - i == 1, i.e., there are only 2 characters, we only need to determine whether these 2 characters are the same. When j - i == 2, i.e., there are only 3 characters, we only need to determine whether the 2 symmetric characters other than the center are equal. In each loop, dynamically maintain and save the longest palindromic substring. Time complexity O(n^2), space complexity O(n^2).

  • Solution 2: center expansion method. In the dynamic programming method, we determine every string within any start and end range. In fact, this is unnecessary; if it is not the longest palindromic substring, there is no need to determine and save the result. Therefore, the dynamic programming method still has room for optimization in terms of space complexity. A core issue in determining a palindrome is finding the “axis”. If the length is even, then the axis is the virtual center; if the length is odd, then the axis is exactly the letter at the center. The idea of the center expansion method is to enumerate the position of each axis. Then make two assumptions: assume the longest palindromic substring is even, then expand to both sides from the virtual center; assume the longest palindromic substring is odd, then expand to both sides from the character at the exact center. The expansion process is the process of symmetrically determining whether the characters on both sides are equal. This method has the same time complexity as dynamic programming, but the space complexity is reduced. Time complexity O(n^2), space complexity O(1).

  • Solution 3: sliding window. This implementation is actually the center expansion method written in a different way. Center expansion enumerates each axis in sequence. The sliding window method optimizes slightly: for some axes whose characters on both sides are not equal, these axes that cannot form a palindromic substring will not be enumerated next time. However, this optimization does not improve the time complexity. Time complexity O(n^2), space complexity O(1).

  • Solution 4: Manacher’s algorithm. This algorithm is the optimal solution to this problem and also the most complex solution. Time complexity O(n), space complexity O(n). The center expansion method has 2 places with repeated determinations. The first is that it expands to both sides every time; different centers expand multiple times, and in fact many characters are repeatedly determined. Can we avoid repeated determinations? The second is: can the center be chosen by jumping instead of enumerating every time? Can we use the information from the previous time to jump to choose the next center? Manacher’s algorithm optimizes the repeated determination problem by adding an auxiliary array, reducing the time complexity from O(n^2) to O(n), trading space for time, and increasing the space complexity to O(n).

    https://img.halfrost.com/Leetcode/leetcode_5_1.png

  • First is preprocessing: add a special character # to the beginning and end of the string and between every two characters. For example, the string aaba becomes #a#a#b#a# after processing. Then the original even-length palindromic string aa becomes the odd-length palindromic string #a#a#, while the odd-length palindromic string aba becomes the still odd-length palindromic string #a#b#a#. After preprocessing, all of them become odd-length strings. Note that the special character here does not need to be a letter that has not appeared; any character can also be used as this special character. This is because when we only consider odd-length palindromic strings, the parity of the two characters we compare each time must be the same, so characters in the original string will not be compared with the inserted special characters, and no problem will occur because of this. After preprocessing, the number of expansion steps from a certain center is equal to the actual string length. Because the radius includes the inserted special characters, and due to the property of left-right symmetry, the expansion radius is equal to the length of the original palindromic substring.

    https://img.halfrost.com/Leetcode/leetcode_5_2.png

  • The core part is how to use the data already scanned on the left to derive the next center on the right to expand from. Here, define the index of the next center to expand from as i. If i is greater than maxRight, we can only continue with center expansion. If i is less than maxRight, there are 3 cases. The three cases are shown in the figure above. Summarizing the above 3 cases gives: dp[i] = min(maxRight-i, dp[2*center-i]), where mirror is symmetric to i with respect to center, so its index can be calculated as 2*center-i. After updating dp[i], center expansion must be performed. After center expansion, dynamically maintain the longest palindromic substring and accordingly update center, maxRight, and record the starting position begin and maxLen in the original string.

Code #

package leetcode

// Solution 1: Manacher's algorithm, time complexity O(n), space complexity O(n)
func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}
	newS := make([]rune, 0)
	newS = append(newS, '#')
	for _, c := range s {
		newS = append(newS, c)
		newS = append(newS, '#')
	}
	// dp[i]:    the palindrome radius centered at index i in the preprocessed string (excluding the center for odd length)
	// maxRight: the rightmost index that can be expanded to by center expansion
	// center:   the index of the center character corresponding to maxRight
	// maxLen:   record the radius of the longest palindrome
	// begin:    record the starting index of the longest palindrome in the original string s
	dp, maxRight, center, maxLen, begin := make([]int, len(newS)), 0, 0, 1, 0
	for i := 0; i < len(newS); i++ {
		if i < maxRight {
			// This line of code is the key to Manacher's algorithm
			dp[i] = min(maxRight-i, dp[2*center-i])
		}
		// Update dp[i] with the center expansion method
		left, right := i-(1+dp[i]), i+(1+dp[i])
		for left >= 0 && right < len(newS) && newS[left] == newS[right] {
			dp[i]++
			left--
			right++
		}
		// Update maxRight, which is the maximum i + dp[i] among the traversed i values
		if i+dp[i] > maxRight {
			maxRight = i + dp[i]
			center = i
		}
		// Record the length of the longest palindromic substring and its corresponding starting point in the original string
		if dp[i] > maxLen {
			maxLen = dp[i]
			begin = (i - maxLen) / 2 // Divide by 2 here because of the auxiliary character # we inserted
		}
	}
	return s[begin : begin+maxLen]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// Solution 2: sliding window, time complexity O(n^2), space complexity O(1)
func longestPalindrome1(s string) string {
	if len(s) == 0 {
		return ""
	}
	left, right, pl, pr := 0, -1, 0, 0
	for left < len(s) {
		// Move to the rightmost identical letter (if there are identical letters)
		for right+1 < len(s) && s[left] == s[right+1] {
			right++
		}
		// Find the boundary of the palindrome
		for left-1 >= 0 && right+1 < len(s) && s[left-1] == s[right+1] {
			left--
			right++
		}
		if right-left > pr-pl {
			pl, pr = left, right
		}
		// Reset to the center for the next palindrome search
		left = (left+right)/2 + 1
		right = left
	}
	return s[pl : pr+1]
}

// Solution 3: center expansion method, time complexity O(n^2), space complexity O(1)
func longestPalindrome2(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		res = maxPalindrome(s, i, i, res)
		res = maxPalindrome(s, i, i+1, res)
	}
	return res
}

func maxPalindrome(s string, i, j int, res string) string {
	sub := ""
	for i >= 0 && j < len(s) && s[i] == s[j] {
		sub = s[i : j+1]
		i--
		j++
	}
	if len(res) < len(sub) {
		return sub
	}
	return res
}

// Solution 4: DP, time complexity O(n^2), space complexity O(n^2)
func longestPalindrome3(s string) string {
	res, dp := "", make([][]bool, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}
	for i := len(s) - 1; i >= 0; i-- {
		for j := i; j < len(s); j++ {
			dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])
			if dp[i][j] && (res == "" || j-i+1 > len(res)) {
				res = s[i : j+1]
			}
		}
	}
	return res
}
  • Languages English
Calendar Jun 25, 2026
Edit Edit this page
Total visits:   You are visitor No.
中文