Longest Palindromic Substring: Expand Around Center, DP, Manacher

Longest Palindromic Substring: Expand Around Center, DP, and Manacher’s Algorithm

Finding the longest palindromic substring of a string is one of the most-asked string problems in coding interviews. It appears at FAANG, AI labs, hedge fund tech teams, and across the broader tech interview circuit because it tests several skills cleanly: recognizing the substructure of palindromes, choosing the right complexity vs simplicity trade-off, and writing the indexing carefully. This guide covers the three standard approaches — expand around center, dynamic programming, and Manacher’s algorithm — with working code, complexity analysis, and the variations interviewers frequently ask as follow-ups.

Problem Statement

Given a string s, return the longest substring of s that reads the same forwards and backwards. If there are multiple longest palindromes, return any one (or the first by convention).

Examples:

• "babad" → "bab" or "aba"
• "cbbd" → "bb"
• "a" → "a"
• "forgeeksskeegfor" → "geeksskeeg"

Approach 1: Expand Around Center (Standard Interview Answer)

Every palindrome has a center. A palindrome of odd length has a single character as its center; a palindrome of even length has the gap between two characters as its center. For a string of length n, there are 2n - 1 possible centers (n single-character centers plus n-1 between-character gaps).

For each center, expand outward as long as the characters match. Track the longest expansion seen.

def longest_palindrome(s: str) -> str:
    """O(n^2) time, O(1) space — expand around each center."""
    if not s:
        return ""

    start = end = 0

    def expand(left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1  # length of the palindrome found

    for i in range(len(s)):
        len1 = expand(i, i)        # odd-length center
        len2 = expand(i, i + 1)    # even-length center
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2

    return s[start:end + 1]


# Tests
print(longest_palindrome("babad"))           # "bab" or "aba"
print(longest_palindrome("cbbd"))            # "bb"
print(longest_palindrome("a"))               # "a"
print(longest_palindrome("forgeeksskeegfor")) # "geeksskeeg"

Complexity: O(n²) time (each of 2n-1 centers expands up to O(n) characters), O(1) extra space.

This is the answer most interviewers expect. Clean, easy to reason about, easy to write correctly under pressure.

Approach 2: Dynamic Programming

Define dp[i][j] = True if s[i..j] is a palindrome. Base cases: single characters (dp[i][i] = True) and adjacent equal pairs (dp[i][i+1] = True if s[i] == s[i+1]). Recurrence: dp[i][j] = dp[i+1][j-1] AND s[i] == s[j].

def longest_palindrome_dp(s: str) -> str:
    """O(n^2) time, O(n^2) space — DP."""
    n = len(s)
    if n == 0:
        return ""

    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # Single characters
    for i in range(n):
        dp[i][i] = True

    # Pairs
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_len = i, 2

    # Substrings of length 3+
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length

    return s[start:start + max_len]

Complexity: O(n²) time and O(n²) space. Same time as expand-around-center but worse space. The trade-off: DP makes the recurrence explicit, which some interviewers find clearer for didactic purposes; expand-around-center is simpler in practice.

Approach 3: Manacher’s Algorithm (O(n))

Manacher’s algorithm computes the longest palindrome in linear time by reusing information from previously-computed palindromes. The idea: when expanding around a new center, if that center lies inside an already-computed palindrome, you can mirror the result rather than recompute from scratch.

Manacher’s transforms the string by inserting a separator character between every pair of characters (and at the start and end), turning every palindrome — odd or even — into an odd-length palindrome in the transformed string. Then it computes a palindrome-radius array linearly using the mirror trick.

def longest_palindrome_manacher(s: str) -> str:
    """O(n) time via Manacher's algorithm."""
    if not s:
        return ""

    # Transform: insert '#' between every char
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n  # p[i] = palindrome radius at center i
    center = right = 0

    for i in range(n):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
               and t[i + p[i] + 1] == t[i - p[i] - 1]):
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]

    # Find max
    max_center = max(range(n), key=lambda i: p[i])
    max_len = p[max_center]
    start = (max_center - max_len) // 2
    return s[start:start + max_len]

Complexity: O(n) time, O(n) space. Strictly better asymptotically than the previous approaches but with much higher constant factors and significantly more complex code. Worth knowing exists; rarely the expected interview answer unless explicitly asked for linear time.

Common Variations

Count all palindromic substrings

(LeetCode #647) Same expand-around-center technique, but count rather than track max:

def count_palindromic_substrings(s: str) -> int:
    """Count all palindromic substrings."""
    count = 0
    for i in range(len(s)):
        for left, right in [(i, i), (i, i + 1)]:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
    return count


print(count_palindromic_substrings("abc"))  # 3
print(count_palindromic_substrings("aaa"))  # 6

Palindrome partitioning

(LeetCode #131, #132) Partition the string into palindromic substrings — either enumerate all partitions (backtracking) or find the minimum cuts (DP). Often a follow-up after this question.

Longest palindromic subsequence

(LeetCode #516) Different problem: find the longest subsequence (non-contiguous) that is a palindrome. Standard DP: O(n²). Distinct from substring; some interviewers ask both to test that you spot the difference.

Shortest palindrome

(LeetCode #214) Add the minimum number of characters to the front of a string to make it a palindrome. Reduces to finding the longest palindromic prefix; can be solved with KMP failure function in O(n).

Common Mistakes

• Forgetting even-length centers. The most common bug. The center of an even-length palindrome is between two characters, not on a character. Implementations that only check single-character centers miss "abba" and similar.
• Off-by-one in index extraction. When expand returns the length, computing the start index requires start = i - (max_len - 1) // 2, not start = i - max_len // 2. Test on both odd and even cases.
• Returning the length instead of the substring. The problem asks for the substring; returning just the length is a partial answer. Read the prompt carefully.
• Quadratic space when not needed. Using DP when expand-around-center is simpler unnecessarily inflates space complexity. Choose the right tool.
• Trying Manacher’s under pressure. Manacher’s is hard to write correctly without practice. Unless the interviewer specifically asks for O(n), use expand-around-center; the time savings of “I tried but it didn’t work” are negative.

Frequently Asked Questions

See also: Removing a Character from a String • Serialize and Deserialize a Binary Tree • Right Rotate an Array by K Elements

function longestPalindrome(s) {
    if (!s || s.length < 1) return "";

    let start = 0;
    let maxLength = 0;

    // Helper function to expand around center
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        // Return length of palindrome
        return right - left - 1;
    }

    for (let i = 0; i < s.length; i++) {
        // Check for odd-length palindromes (single character center)
        let len1 = expandAroundCenter(i, i);

        // Check for even-length palindromes (pair of characters)
        let len2 = expandAroundCenter(i, i + 1);

        // Take the longer one
        let len = Math.max(len1, len2);

        // Update if we found a longer palindrome
        if (len > maxLength) {
            maxLength = len;
            // Calculate start position
            start = i - Math.floor((len - 1) / 2);
        }
    }

    return s.substring(start, start + maxLength);
}

// Test cases:
console.log(longestPalindrome("babad"));       // "bab" or "aba"
console.log(longestPalindrome("cbbd"));        // "bb"
console.log(longestPalindrome("racecar"));     // "racecar"
console.log(longestPalindrome("noon"));        // "noon"
console.log(longestPalindrome("a"));           // "a"

function longestPalindrome(s) {
    const n = s.length;
    if (n < 2) return s;

    // dp[i][j] = true if substring from i to j is palindrome
    const dp = Array(n).fill(null).map(() => Array(n).fill(false));

    let start = 0;
    let maxLength = 1;

    // Every single character is a palindrome
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Check for 2-character palindromes
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }

    // Check for palindromes of length 3 and greater
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i < n - len + 1; i++) {
            let j = i + len - 1;

            // Check if s[i...j] is palindrome
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }

    return s.substring(start, start + maxLength);
}