2.13 Palindromes

A palindrome is a sequence that reads the same forward and backward. In array and string algorithms, palindrome problems usually reduce to symmetric comparison, center expansion, dynamic programming, or hashing.

For strings, first decide whether the unit of comparison is a byte, a Unicode code point, or a normalized user-visible character. The examples here use byte strings for clarity.

Problem

Given a string s, determine whether it is a palindrome, find palindromic substrings, or compute the longest palindromic substring.

Examples:

"racecar"    palindrome
"abba"       palindrome
"abca"       not a palindrome

Basic Palindrome Check

Use two pointers from opposite ends.

func IsPalindrome(s string) bool {
	l := 0
	r := len(s) - 1

	for l < r {
		if s[l] != s[r] {
			return false
		}
		l++
		r--
	}

	return true
}

Invariant:

Before each iteration, all pairs outside [l, r] have already been checked and are equal.

If the loop finishes, no mismatched pair exists.

Complexity:

Time:  O(n)
Space: O(1)

Ignoring Non-Alphanumeric Characters

A common variant ignores punctuation and case.

func IsCleanPalindromeASCII(s string) bool {
	l := 0
	r := len(s) - 1

	for l < r {
		for l < r && !isAlnumASCII(s[l]) {
			l++
		}
		for l < r && !isAlnumASCII(s[r]) {
			r--
		}

		if lowerASCII(s[l]) != lowerASCII(s[r]) {
			return false
		}

		l++
		r--
	}

	return true
}

func isAlnumASCII(c byte) bool {
	return ('a' <= c && c <= 'z') ||
		('A' <= c && c <= 'Z') ||
		('0' <= c && c <= '9')
}

func lowerASCII(c byte) byte {
	if 'A' <= c && c <= 'Z' {
		return c + ('a' - 'A')
	}
	return c
}

The invariant is the same, except skipped characters do not participate in comparison.

Longest Palindrome by Center Expansion

Every palindrome has a center. Odd-length palindromes are centered at one character. Even-length palindromes are centered between two characters.

func LongestPalindromeExpand(s string) string {
	if len(s) == 0 {
		return ""
	}

	bestL := 0
	bestR := 1

	for i := 0; i < len(s); i++ {
		l1, r1 := expand(s, i, i+1)
		if r1-l1 > bestR-bestL {
			bestL, bestR = l1, r1
		}

		l2, r2 := expand(s, i, i)
		if r2-l2 > bestR-bestL {
			bestL, bestR = l2, r2
		}
	}

	return s[bestL:bestR]
}

func expand(s string, l, r int) (int, int) {
	for l >= 0 && r < len(s) && s[l] == s[r] {
		l--
		r++
	}
	return l + 1, r
}

This implementation uses half-open output ranges [l, r).

For even-length centers, call:

expand(s, i, i+1)

For odd-length centers, call:

expand(s, i, i)

Complexity:

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

Counting Palindromic Substrings

Use the same center expansion and count every successful expansion.

func CountPalSubstrings(s string) int {
	count := 0

	for i := 0; i < len(s); i++ {
		count += countFromCenter(s, i, i)
		count += countFromCenter(s, i, i+1)
	}

	return count
}

func countFromCenter(s string, l, r int) int {
	count := 0

	for l >= 0 && r < len(s) && s[l] == s[r] {
		count++
		l--
		r++
	}

	return count
}

Each successful expansion corresponds to one palindromic substring.

Dynamic Programming

Define:

dp[l][r] = true if s[l:r+1] is a palindrome

Then:

dp[l][r] = s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1])

Implementation:

func LongestPalindromeDP(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}

	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}

	bestL := 0
	bestLen := 1

	for length := 1; length <= n; length++ {
		for l := 0; l+length <= n; l++ {
			r := l + length - 1

			if s[l] == s[r] && (length <= 2 || dp[l+1][r-1]) {
				dp[l][r] = true
				if length > bestLen {
					bestL = l
					bestLen = length
				}
			}
		}
	}

	return s[bestL : bestL+bestLen]
}

Complexity:

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

This method is useful when later queries need to ask whether arbitrary substrings are palindromes.

Longest Palindrome in Linear Time

Manacher’s algorithm computes palindrome radii in linear time. It transforms the string so that odd and even palindromes can be handled uniformly.

For most application code, center expansion is simpler and fast enough. Use Manacher’s algorithm when n is large and worst-case quadratic behavior is unacceptable.

Palindrome by Hashing

A substring is a palindrome if its forward hash equals its reverse hash. This supports many palindrome queries after preprocessing.

The method is probabilistic unless a collision-free representation is used. Always use direct verification when exact correctness is required.

Common Pitfalls

The most common off-by-one error is mixing inclusive [l, r] and half-open [l, r) ranges. Keep the convention fixed.

In center expansion, odd centers use (i, i) and even centers use (i, i+1). Reversing these calls misses cases.

Byte-based palindrome logic can break on Unicode text. For Unicode code points, convert to []rune. For human-facing text, normalization and grapheme clusters may be required.

Case-insensitive comparison requires normalization. ASCII lowercasing only handles ASCII letters.

Hash-based palindrome checks can collide. Use them only when the collision model is acceptable or when a final exact comparison is performed.

Takeaway

Palindrome algorithms compare symmetric positions. Use two pointers for a full-string check, center expansion for longest or counted palindromic substrings, dynamic programming for repeated substring queries, and Manacher’s algorithm when linear worst-case time is required.