Chuỗi con đối xứng dài nhất (Longest Palindromic Substring)

5. Longest Palindromic Substring

Đề bài

Cho một chuỗi s, hãy trả về chuỗi con đối xứng (palindromic substring) dài nhất trong s.

Ví dụ 1:

Input: s = "babad"
Output: "bab"
Note: "aba" là đáp án sai.

Ví dụ 2:

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

Ví dụ 3:

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

Ví dụ 4:

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

Ràng buộc:

  • 1 <= s.length <= 1000
  • s chỉ gồm chữ số và chữ cái tiếng Anh (chữ thường và/hoặc chữ hoa)

Tóm tắt đề

Cho bạn một chuỗi s, hãy tìm chuỗi con đối xứng (palindrome) dài nhất trong s.

Ý tưởng

  • Đây là một bài rất “kinh điển” và có nhiều hướng giải.

  • Cách 1 — Quy hoạch động (dynamic programming, DP): Đặt dp[i][j] cho biết chuỗi con từ ký tự thứ i đến j có phải là palindrome hay không. Tính chất quan trọng: nếu một chuỗi là palindrome, bỏ đi 2 đầu (khi chúng giống nhau) thì phần còn lại vẫn là palindrome. Do đó: dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])

    • Với j-i == 1 (độ dài 2): chỉ cần kiểm tra 2 ký tự có giống nhau không.
    • Với j-i == 2 (độ dài 3): chỉ cần kiểm tra 2 ký tự đối xứng quanh tâm. Mỗi vòng lặp ta cập nhật và lưu lại palindrome dài nhất. Độ phức tạp: thời gian O(n2)O(n^2), bộ nhớ O(n2)O(n^2).

  • Cách 2 — Nở từ tâm (center expansion): DP kiểm tra rất nhiều đoạn không cần thiết. Để tối ưu bộ nhớ, ta tập trung vào “tâm” của palindrome:

    • Nếu độ dài palindrome là lẻ, tâm là một ký tự thật.
    • Nếu độ dài palindrome là chẵn, tâm nằm giữa 2 ký tự (tâm “ảo”). Ta lần lượt thử mọi tâm, rồi nở ra hai phía khi hai ký tự đối xứng còn bằng nhau. Độ phức tạp: thời gian O(n2)O(n^2), bộ nhớ O(1)O(1).

  • Cách 3 — Cửa sổ trượt (sliding window): Thực chất là một biến thể viết khác của center expansion. Có tối ưu nhẹ: nếu một số tâm “chắc chắn không thể” tạo palindrome dài (hai bên lệch ngay), lần sau có thể bỏ qua. Dù vậy độ phức tạp vẫn là thời gian O(n2)O(n^2), bộ nhớ O(1)O(1).

  • Cách 4 — Thuật toán Manacher (Manacher's algorithm): Đây là lời giải tối ưu cho bài này, thời gian O(n)O(n), bộ nhớ O(n)O(n). Ý tưởng là tận dụng thông tin từ các tâm trước đó để:

    • Tránh so sánh lặp lại khi nở từ tâm.

    • “Nhảy” tâm hợp lý dựa trên đối xứng, thay vì thử lại từ đầu.

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

  • Tiền xử lý (preprocess): chèn một ký tự đặc biệt # vào đầu/cuối và giữa mỗi cặp ký tự. Ví dụ aaba → #a#a#b#a#.

    • Palindrome chẵn như aa sẽ biến thành palindrome lẻ #a#a#.

    • Palindrome lẻ như aba vẫn là palindrome lẻ #a#b#a#. Nhờ vậy ta chỉ cần xử lý trường hợp palindrome có độ dài lẻ. Lưu ý: ký tự đặc biệt không nhất thiết phải là ký tự “chưa từng xuất hiện”, có thể dùng bất kỳ ký tự nào. Lý do: trong chuỗi đã chèn #, khi so sánh đối xứng, các ký tự sẽ được so “đúng loại” (ký tự gốc so với ký tự gốc, # so với #), nên không gây sai lệch. Sau tiền xử lý, “bán kính nở” quanh một tâm tương ứng trực tiếp với độ dài palindrome trong chuỗi gốc.

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

  • Phần cốt lõi: dùng thông tin đã quét ở bên trái để suy ra tâm cần nở tiếp theo ở bên phải. Gọi chỉ số đang xét là i:

    • Nếu i > maxRight thì không có thông tin “kế thừa”, ta phải nở từ tâm như bình thường.
    • Nếu i < maxRight thì dựa vào tâm đối xứng (mirror) qua center để có bán kính ban đầu: dp[i] = min(maxRight-i, dp[2*center-i]) Trong đó 2*center-i chính là vị trí đối xứng của i qua center. Sau khi có bán kính ban đầu, ta tiếp tục nở từ tâm để cập nhật chính xác, rồi đồng thời cập nhật center, maxRight, và lưu lại vị trí bắt đầu begin cùng độ dài lớn nhất maxLen trong chuỗi gốc.

Code

package leetcode

// Cách 1: Manacher's algorithm — thời gian O(n), bộ nhớ 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]:    bán kính palindrome (trên chuỗi đã tiền xử lý) với tâm tại i (không tính ký tự tâm)
	// maxRight: rìa phải xa nhất có thể vươn tới hiện tại
	// center:   tâm tương ứng với maxRight
	// maxLen:   bán kính lớn nhất (tương ứng palindrome dài nhất)
	// begin:    vị trí bắt đầu của palindrome dài nhất trong chuỗi gốc s
	dp, maxRight, center, maxLen, begin := make([]int, len(newS)), 0, 0, 1, 0
	for i := 0; i < len(newS); i++ {
		if i < maxRight {
			// Dòng này là “linh hồn” của Manacher
			dp[i] = min(maxRight-i, dp[2*center-i])
		}
		// Nở từ tâm để cập nhật dp[i]
		left, right := i-(1+dp[i]), i+(1+dp[i])
		for left >= 0 && right < len(newS) && newS[left] == newS[right] {
			dp[i]++
			left--
			right++
		}
		// Cập nhật maxRight (là max của i + dp[i] trong quá trình duyệt)
		if i+dp[i] > maxRight {
			maxRight = i + dp[i]
			center = i
		}
		// Lưu lại palindrome dài nhất và vị trí bắt đầu trong chuỗi gốc
		if dp[i] > maxLen {
			maxLen = dp[i]
			begin = (i - maxLen) / 2 // Chia 2 vì trong newS có ký tự chèn '#'
		}
	}
	return s[begin : begin+maxLen]
}

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

// Cách 2: Cửa sổ trượt (sliding window) — thời gian O(n^2), bộ nhớ O(1)
func longestPalindrome1(s string) string {
	if len(s) == 0 {
		return ""
	}
	left, right, pl, pr := 0, -1, 0, 0
	for left < len(s) {
		// Nhảy tới vị trí xa nhất bên phải vẫn còn ký tự giống nhau (nếu có)
		for right+1 < len(s) && s[left] == s[right+1] {
			right++
		}
		// Nở ra hai phía để tìm biên 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 sang “tâm” tiếp theo để tìm palindrome mới
		left = (left+right)/2 + 1
		right = left
	}
	return s[pl : pr+1]
}

// Cách 3: Nở từ tâm (center expansion) — thời gian O(n^2), bộ nhớ 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
}

// Cách 4: DP — thời gian O(n^2), bộ nhớ 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
}