Longest Palindromic Substring

We've explored three fundamentally different approaches to finding the longest palindromic substring: the brute force O(n³) enumeration, the elegant expand-around-center O(n²) technique, and the sophisticated Manacher's O(n) algorithm. Each represents a different trade-off between simplicity, efficiency, and implementation complexity.

In real-world software engineering and technical interviews, knowing which algorithm to use is as important as knowing how to implement them. The "best" algorithm depends on your constraints: input size, time limits, development time available, and code maintainability requirements.

This page synthesizes everything we've learned, providing a comprehensive framework for algorithm selection and a deep understanding of the trade-offs involved.

Let's begin with a comprehensive comparison table that summarizes all the approaches we've studied.

Note on Dynamic Programming:

We haven't explicitly covered the DP approach in this module, but it's worth mentioning for completeness:

• Create a 2D boolean table dp[i][j] where dp[i][j] = true if s[i:j+1] is a palindrome
• Fill the table using the recurrence: dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]
• Base cases: dp[i][i] = true (single char), dp[i][i+1] = (s[i] == s[i+1]) (two chars)

The DP approach has the same O(n²) time as expand-around-center but uses O(n²) space, making expand-around-center strictly superior for this problem. However, DP tables are useful when you need to answer multiple queries about different substrings.

Understanding the practical implications of O(n³), O(n²), and O(n) requires examining actual operation counts and real-world execution times.

Operation Count Analysis:

For a string of length n, the approximate number of primitive operations (character comparisons) is:

• Brute Force O(n³): ~n³/6 comparisons
• Expand Around Center O(n²): ~n²/4 comparisons (average case), ~n²/2 (worst case)
• Manacher's O(n): ~2n comparisons (exactly)

The constants matter! Brute force's 1/6 constant doesn't save it from being 6× slower than pure n³, but Manacher's 2× constant is negligible.

Space complexity is often the forgotten sibling of time complexity, but in practice, memory constraints can be as limiting as time constraints.

Memory Usage Breakdown:

Key Observations:

1. Brute Force and Expand-Around-Center are optimal for space. They use only a constant number of variables regardless of input size.

2. Dynamic Programming is space-prohibitive for large inputs. At n = 100,000, the DP table requires 10 GB of memory—more than most systems have. At n = 1,000,000, it requires 1 TB, which is infeasible.

3. Manacher's has a modest O(n) space overhead. The P array and transformed string together use about 4× the input size in bytes. This is very manageable even for multi-megabyte strings.

4. Memory hierarchy effects. The O(1) space algorithms keep all working data in CPU cache, while O(n²) DP suffers from cache misses as the table grows beyond L3 cache size (~10-50 MB typically).

Asymptotic complexity describes worst-case behavior, but real-world inputs often have average-case characteristics that differ significantly.

Expand-Around-Center: Input-Dependent Performance

The O(n²) complexity of expand-around-center is the worst case, occurring when every expansion from every center goes to the string boundaries. This happens with strings like:

• "aaaa...a" (all identical characters)
• Full palindromes like "abcba..."

For random strings, most expansions terminate quickly (after 1-2 steps) because random characters are unlikely to match. Average case for random strings is closer to O(n).

Manacher's Algorithm: Consistent O(n)

Manacher's algorithm has the same O(n) complexity regardless of input structure. Whether the input is random, all identical, or a complex palindrome, the amortized analysis guarantees exactly O(n) work. This predictability is valuable in systems where worst-case latency matters.

Beyond asymptotic complexity, engineers must consider implementation complexity—how difficult is the algorithm to code correctly, understand, and maintain?

Lines of Code (Approximate):

Common Bugs by Algorithm:

Brute Force:

• Off-by-one in substring extraction
• Forgetting to handle empty string

Expand Around Center:

• Wrong formula for start position: start = i - (len - 1) / 2
• Forgetting even-length case
• Integer division issues with negative values

Dynamic Programming:

• Wrong initialization of base cases
• Incorrect loop ordering (must fill by increasing length)
• Index confusion between dp[i][j] and string positions

Manacher's:

• Off-by-one in mirror calculation
• Incorrect boundary conditions in expansion
• Wrong conversion between transformed and original indices
• Using > vs >= in R comparison
• Forgetting to update C and R

Given the trade-offs we've analyzed, here's a practical decision framework for selecting the appropriate algorithm.

Flowchart Logic:

Start → Is n ≤ 500?
  └─ Yes → Use Expand Around Center (simple & fast enough)
  └─ No → Is n ≤ 10,000?
           └─ Yes → Use Expand Around Center (O(n²) is fine)
           └─ No → Is there a tight time limit?
                    └─ No → Use Expand Around Center (acceptable)
                    └─ Yes → Is correctness critical?
                              └─ Yes → Use Manacher's (guaranteed O(n))
                              └─ No → Consider Manacher's, but EAC may work

The techniques we've learned extend to related palindrome problems. Understanding these connections deepens your algorithmic toolkit.

Problem 1: Count All Palindromic Substrings

Instead of finding the longest palindrome, count the total number of palindromic substrings.

• Brute Force: O(n³) — check all n² substrings
• Expand Around Center: O(n²) — sum all expansion lengths
• Manacher's: O(n) — sum of P array gives count (with adjustment)

Problem 2: Longest Palindromic Subsequence

Find the longest subsequence (not substring) that is a palindrome. Characters don't need to be contiguous.

"character" → "carac" (length 5)

• Solution: Dynamic programming with O(n²) time and space
• Cannot use Manacher's: The center-expansion approach doesn't apply to subsequences

Problem 3: Minimum Insertions to Make Palindrome

Find the minimum characters to insert to make the entire string a palindrome.

• Solution: n - LPS (Longest Palindromic Subsequence length)
• Insight: The LPS doesn't need modification; insert the rest symmetrically

Let's look at actual benchmark results to validate our theoretical analysis. The following results are from running each algorithm on strings of varying sizes and types.

Test Environment: Modern laptop, single-threaded execution, Python implementation

Test Strings:

1. Random: Random lowercase letters
2. Periodic: Repeating "abc" pattern
3. All Same: All 'a' characters (worst case for EAC)
4. Real Text: English text sample

Technical interviews featuring the LPS problem often reveal predictable patterns of mistakes. Learn from these common errors:

We've comprehensively analyzed the time-space trade-offs for solving the longest palindromic substring problem. Here are the key takeaways:

Congratulations!

You've completed the Longest Palindromic Substring module. You now understand:

• The problem formalization and why it matters
• The brute force approach and its O(n³) limitations
• The elegant expand-around-center O(n²) technique
• The sophisticated Manacher's O(n) algorithm
• When to use each approach based on constraints

These techniques extend to many string problems. The pattern of "start simple, identify redundancy, optimize" applies far beyond palindromes.