Four Ways to Find the Longest Palindrome, from O(n³) to O(n)

After conquering the longest substring without repeating characters (LC 3), let's strike while the iron is hot and look at another "cornerstone" of the string domain — LeetCode 5. Longest Palindromic Substring.

This problem is also rated Medium, but it appears with extremely high frequency in interviews at ByteDance, Tencent, Google, and Amazon. It is not only the "parent problem" for palindrome string questions but also an excellent battleground for two classic algorithmic ideas: dynamic programming and center expansion.

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

Today, we will follow a path "from inefficient to efficient," step by step, dissecting four solutions to this problem: Brute Force, Dynamic Programming, Center Expansion, and the legendary Manacher's Algorithm. After reading this, you will find that the history of solutions to the palindrome substring problem is itself a wonderful chronicle of algorithmic evolution.

Core Difficulty: How to Efficiently "Find Palindromes"?

The characteristic of a palindrome string is central symmetry, such as "aba" or "abba". The most naive idea for determining whether a substring is a palindrome is to compare characters from both ends towards the middle. The problem is, if we apply this check to all substrings, the time complexity will be a disastrous O(n^3).

Therefore, the core challenge of this problem is: How can we leverage the properties of palindromes to avoid redundant comparisons, thereby finding the answer in O(n^2) or even O(n) time?

Level 1: Brute Force — The Most Intuitive "Carpet Search"

This is the starting point of our thinking. The idea is simple: enumerate all substrings, check if each is a palindrome, and record the longest one.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        int maxLen = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j) && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

• Time Complexity: O(n^3). The two nested loops enumerating all substrings are O(n^2), and each palindrome check is O(n).
• Space Complexity: O(1).

Commentary: This solution will directly time out on LeetCode, but it helps us understand the essence of the problem. All subsequent optimizations revolve around how to reduce redundant comparisons.

Level 2: Dynamic Programming — A Classic Case of "Trading Space for Time"

Brute force is slow because when checking a long palindrome, it redundantly re-checks its inner substrings. If we can remember the states of these substrings, we can avoid redundant work.

Core Idea

If a substring is a palindrome, and the two new characters obtained by expanding one character outward from both its head and tail are also equal, then the new expanded substring must also be a palindrome.

This property can be described by a state transition equation:

Let dp[i][j] represent whether the substring s[i..j] is a palindrome.

• When s[i] == s[j]: dp[i][j] = dp[i+1][j-1].
• When s[i] != s[j]: dp[i][j] = false.

Boundary conditions: A single character (j - i < 1) or two identical characters (j - i == 1) are both palindromes.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1, start = 0;

        for (int i = n - 1; i >= 0; i--) { // Iterate from bottom to top
            for (int j = i; j < n; j++) {  // Iterate from left to right
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) { // Boundary case: length 1 or 2
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

• Time Complexity: O(n^2). Fills an n x n 2D array.
• Space Complexity: O(n^2). Used to store the dp table.

Commentary: This is a very standard dynamic programming solution with clear logic. However, the O(n^2) space complexity is still a burden when n is large (e.g., n=1000).

Level 3: Center Expansion — "Dimensionality Reduction" by Discarding the 2D Table

Although dynamic programming is fast, it requires an extra 2D array. Can we achieve the same effect using O(1) space?

Core Idea

Palindromes are centrally symmetric. So, why not expand directly from the center outwards?

A string of length n has 2n-1 possible palindrome centers:

• n centers for odd-length palindromes: each single character.
• n-1 centers for even-length palindromes: the space between two adjacent characters.

We iterate through all possible centers, expand outwards from each center until a palindrome can no longer be formed, and record the longest one.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // Center at s[i], odd-length expansion
            int len1 = expandAroundCenter(s, i, i);
            // Center between s[i] and s[i+1], even-length expansion
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // Return the length of the expanded palindrome
        return right - left - 1;
    }
}

• Time Complexity: O(n^2). In the worst case, each center might expand O(n) times.
• Space Complexity: O(1). Only a constant number of variables are used.

Commentary: This is the most recommended solution for interviews. It achieves a perfect balance between O(n^2) time complexity and O(1) space complexity. The code is concise, the logic is clear, and it is the "Swiss Army knife" for solving such problems.

Level 4: Manacher's Algorithm — The O(n) Time Complexity "Heavy Hitter"

If you feel O(n^2) is not fast enough, then Manacher's Algorithm is the ultimate answer. It leverages the symmetry of palindromes to reduce the time complexity to an astonishing O(n).

Core Idea

1. Unify Parity: Insert a special character (like #) at the beginning, end, and between every character of the original string. This transforms all palindromic substrings into odd-length ones. For example, "aba" becomes "#a#b#a#".
2. Leverage Symmetry: Maintain a palindrome radius array pArr[i], representing the radius of the longest palindrome centered at i.
3. Accelerate Expansion: Maintain the current rightmost palindrome boundary R and its corresponding center C. When calculating pArr[i], if i < R, we can use the pArr[j] of its symmetric point j about C to quickly initialize pArr[i], thus avoiding expansion from scratch.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 1. Preprocessing
        T = '#'.join(f'^{s}$') # Add '^' and '$' to prevent out-of-bounds
        n = len(T)
        P = [0] * n
        C = R = 0
        
        # 2. Calculate palindrome radius array
        for i in range(1, n-1):
            # Use symmetry for fast initialization
            mirror = 2 * C - i
            if i < R:
                P[i] = min(R - i, P[mirror])
            
            # Center expansion
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1
            
            # Update rightmost boundary and center
            if i + P[i] > R:
                C, R = i, i + P[i]
        
        # 3. Find the maximum radius and its center
        max_len, center_index = max((n, i) for i, n in enumerate(P))
        # 4. Restore the original string from the expanded string
        return s[(center_index - max_len) // 2: (center_index + max_len) // 2]

• Time Complexity: O(n). Each character is visited at most a constant number of times.
• Space Complexity: O(n). Used to store the expanded string and the radius array.

Commentary: Manacher's Algorithm is the theoretically optimal solution for the longest palindromic substring problem. However, it has a certain barrier to understanding, and the code is relatively complex. In an interview, fluently writing the center expansion method is already excellent. Manacher's Algorithm can be presented as "icing on the cake" — advanced knowledge to demonstrate your depth.

In-Depth Summary: An Evolution Map of the Four Solutions

Solution	Time Complexity	Space Complexity	Core Idea	Interview Recommendation
Brute Force	O(n^3)	O(1)	Enumerate all substrings and verify	⭐ (Only for understanding the problem)
Dynamic Programming	O(n^2)	O(n^2)	Record sub-states to avoid redundant checks	⭐⭐⭐ (Classic logic, large space)
Center Expansion	O(n^2)	O(1)	Expand outwards from the center	⭐⭐⭐⭐⭐ (Most recommended, balanced and elegant)
Manacher's Algorithm	O(n)	O(n)	Use symmetry to accelerate expansion	⭐⭐⭐⭐ (Theoretically optimal, bonus points in interviews)

What Have We Learned from This Problem?

1. The Thinking Path from Brute Force to Optimization: This problem perfectly demonstrates how, by observing the characteristics of the problem (palindrome symmetry), we can step-by-step optimize an algorithm from O(n^3) to O(n).
2. Dynamic Programming's "Space for Time": When you find subproblems being recalculated, consider using dynamic programming to store intermediate states.
3. Center Expansion's "Adaptation to Local Conditions": When dealing with palindrome problems, the O(n^2) center expansion method is often better than dynamic programming because it saves the overhead of a 2D array.
4. Manacher's Algorithm's "Ultimate Pursuit": It tells us that through clever preprocessing and symmetry exploitation, an algorithm that seems impossible to optimize further can be pushed to its theoretical limit.

Some Final Thoughts from the Heart

LeetCode 5 is a very classic problem. It's not just about learning to solve one problem; it's about experiencing the complete process of algorithm optimization. From brute force to dynamic programming, to center expansion, and finally to Manacher, each step represents a new way of thinking.

For interviews, the center expansion method is your "weapon of choice" — it is efficient enough and easy to implement. Manacher's Algorithm, on the other hand, is more of a "secret weapon" you can reveal when you want to demonstrate an ultimate pursuit.

Remember today's mantra:

For the longest palindromic substring, center expansion is the foundation. Dynamic programming is also acceptable, but Manacher's Algorithm is the most invincible.

---

If you feel this solution guide helped you thoroughly understand the longest palindromic substring, feel free to like, bookmark, and share! Our next stop will target LeetCode 53 'Maximum Subarray'. See you there! 🚀