Longest Palindromic Substring: Multiple Solutions and Complexity Analysis

Understanding the Longest Palindromic Substring Problem

A palindrome is a sequence of characters that reads the same forward and backward, such as "racecar" or "madam". The Longest Palindromic Substring (LPS) problem asks us to find the longest contiguous substring within a given string that forms a palindrome. For example, in the string "babad", the longest palindromic substring could be "bab" or "aba" (both length 3). In "cbbd", the answer is "bb".

This problem appears frequently in coding interviews and competitive programming platforms like LeetCode (Problem #5), serving as an excellent benchmark for evaluating a candidate's grasp of string manipulation, dynamic programming, and algorithm optimization.

Problem Statement (Formal Definition)

Given a string s of length n, return the longest palindromic substring in s. If multiple palindromic substrings share the maximum length, any one of them may be returned. The input string consists of printable ASCII characters, and 1 ≤ n ≤ 1000 in typical constraints (though some variations push this higher).

Why Mastering This Problem Matters

Beyond interview preparation, the LPS problem teaches fundamental algorithmic patterns that transfer to real-world engineering:

• Subproblem decomposition — breaking a complex query into overlapping smaller checks (the essence of dynamic programming)
• Space-time tradeoffs — choosing between memory-intensive caching and lean, on-the-fly computation
• Center-expansion techniques — used in palindrome detection, regex-like pattern matching, and even computational biology for finding palindromic sequences in DNA
• Linear-time string algorithms — Manacher's algorithm is a classic example of how clever invariants eliminate redundant work, a mindset applicable to many sliding-window and two-pointer problems

Understanding multiple approaches and their complexity profiles empowers you to select the right tool for the constraints at hand — whether you're optimizing for memory on an embedded device or for raw speed on a server handling millions of requests.

Solution 1: Brute Force — The Starting Point

Intuition

The most straightforward approach enumerates every possible substring and checks if it's a palindrome, tracking the longest one found. A substring is defined by its start and end indices (i, j) where 0 ≤ i ≤ j < n. For each pair, we extract the substring and verify palindrome property by comparing characters from both ends inward.

Code Implementation

def longest_palindrome_bruteforce(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    longest = ""
    
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            # Check if substring is palindrome
            if substring == substring[::-1]:
                if len(substring) > len(longest):
                    longest = substring
    
    return longest

# Example usage
print(longest_palindrome_bruteforce("babad"))  # Output: "bab" or "aba"
print(longest_palindrome_bruteforce("cbbd"))   # Output: "bb"

Complexity Analysis

• Time Complexity: O(n³) — There are O(n²) substrings (roughly n(n+1)/2). For each, the palindrome check via string reversal or two-pointer comparison takes O(n) time. The nested loops and linear check combine to O(n³).
• Space Complexity: O(1) auxiliary space — We only store the current best substring reference (though creating slices in Python technically uses O(k) temporary space per check where k is substring length, which is bounded by O(n)).

This solution is too slow for strings longer than about 100 characters. It serves as a baseline to beat.

Solution 2: Dynamic Programming — Caching Overlapping Checks

Intuition

Notice that checking whether a substring s[i..j] is a palindrome can be done recursively: it's a palindrome if s[i] == s[j] AND the inner substring s[i+1..j-1] is also a palindrome. This overlapping subproblem structure is perfect for dynamic programming. We build a 2D boolean table dp[i][j] where dp[i][j] is True if the substring from index i to j (inclusive) is a palindrome.

Base cases: Every single character is a palindrome (dp[i][i] = True). Two adjacent identical characters form a palindrome of length 2 (dp[i][i+1] = True if s[i] == s[i+1]). For lengths ≥ 3, we use the recurrence dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1].

We iterate over increasing substring lengths, filling the table diagonally. This ensures that when computing dp[i][j], the inner result dp[i+1][j-1] has already been computed.

Code Implementation

def longest_palindrome_dp(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    # dp[i][j] will be True if s[i..j] is a palindrome
    dp = [[False] * n for _ in range(n)]
    
    start = 0
    max_len = 1
    
    # Base case: all substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # Check substrings of length 3 and greater
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # A substring is palindrome if ends match and inner substring is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_len:
                    start = i
                    max_len = length
    
    return s[start:start + max_len]

# Example usage
print(longest_palindrome_dp("babad"))  # Output: "bab" or "aba"
print(longest_palindrome_dp("cbbd"))   # Output: "bb"
print(longest_palindrome_dp("racecar")) # Output: "racecar"

Complexity Analysis

• Time Complexity: O(n²) — We fill an n×n table. The outer loop over lengths and inner loop over start indices together process roughly n²/2 entries, each computed in O(1) time.
• Space Complexity: O(n²) — The DP table stores n² boolean values. For n=1000, this requires about 1 million entries, or ~1 MB, which is acceptable in most contexts but can be improved.

The DP approach is a significant improvement over brute force and demonstrates how caching eliminates redundant computation. However, the O(n²) space requirement can be reduced, as we'll see next.

Solution 3: Expand Around Center — Optimal Quadratic Solution

Intuition

A palindrome mirrors itself around a center. For odd-length palindromes (like "racecar"), the center is a single character. For even-length palindromes (like "abba"), the center lies between two characters. We can exploit this by considering each of the 2n−1 possible centers (n single-character centers and n−1 between-character centers) and expanding outward while the characters on both sides match. This gives us each maximal palindrome anchored at that center. We simply track the longest one seen.

This approach uses no DP table — just a few integer variables — achieving O(1) extra space while maintaining O(n²) time.

Code Implementation

def longest_palindrome_expand_center(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    start = 0
    max_len = 1
    
    def expand_around_center(left: int, right: int) -> tuple[int, int]:
        """Expand from given center and return (start, length) of longest palindrome."""
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        # After loop, left and right are one step beyond the palindrome bounds
        palindrome_length = right - left - 1
        return left + 1, palindrome_length
    
    for i in range(n):
        # Odd-length palindrome: single character center
        l, length = expand_around_center(i, i)
        if length > max_len:
            start = l
            max_len = length
        
        # Even-length palindrome: center between i and i+1
        l, length = expand_around_center(i, i + 1)
        if length > max_len:
            start = l
            max_len = length
    
    return s[start:start + max_len]

# Example usage
print(longest_palindrome_expand_center("babad"))   # Output: "bab" or "aba"
print(longest_palindrome_expand_center("cbbd"))    # Output: "bb"
print(longest_palindrome_expand_center("racecar")) # Output: "racecar"
print(longest_palindrome_expand_center("abba"))    # Output: "abba"

Complexity Analysis

• Time Complexity: O(n²) — We examine 2n−1 centers. In the worst case (string of all identical characters, like "aaaa..."), each expand operation scans from the center to the string boundary, taking up to O(n) time per center. This gives O(n²) total.
• Space Complexity: O(1) — We store only a handful of variables (start, max_len, loop indices). No additional arrays proportional to input size are allocated.

This is widely considered the "sweet spot" solution: asymptotically optimal for the quadratic constraint class, extremely simple to implement, and memory-efficient. In interviews, this is often the expected solution.

Solution 4: Manacher's Algorithm — Linear Time Mastery

Intuition

Can we do better than O(n²)? Yes — Manacher's algorithm (1975) achieves O(n) time by exploiting symmetry to skip redundant expansions. The key insight: when expanding around a new center that lies within a previously discovered larger palindrome, we can use the mirrored expansion length from the opposite side to initialize our search, avoiding redundant character comparisons.

The algorithm first preprocesses the string by inserting a sentinel character (typically '#') between every original character and at the boundaries. This unifies odd and even palindrome handling — every palindrome in the transformed string corresponds to an odd-length palindrome in the transformed space, eliminating the need for separate even/odd logic.

For example, "abba" becomes "#a#b#b#a#". A palindrome centered at the middle '#' between the two 'b's now has odd length in the transformed string.

We maintain three variables as we scan left to right:

• center — the center of the rightmost palindrome found so far
• right_boundary — the right edge of that palindrome
• P[i] — the expansion radius at transformed index i

When we are at a new index i, its mirror across center is at mirror = 2*center - i. If i is within the rightmost palindrome (i < right_boundary), we initialize P[i] to min(right_boundary - i, P[mirror]), then expand further as needed. Otherwise, we start expansion from scratch. After finding the maximal radius at i, we update center and right_boundary if we've extended past the current boundary.

Code Implementation

def longest_palindrome_manacher(s: str) -> str:
    if len(s) == 0:
        return ""
    
    # Transform string: insert '#' between characters and at boundaries
    # Example: "abc" -> "#a#b#c#"
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    
    P = [0] * n          # P[i] = radius of palindrome centered at i in transformed string
    center = 0           # Center of the rightmost palindrome found
    right_boundary = 0   # Right edge of that palindrome
    
    max_center = 0       # Center of the longest palindrome found
    max_radius = 0       # Radius of the longest palindrome found
    
    for i in range(n):
        # Mirror of i across current center: mirror = 2*center - i
        if i < right_boundary:
            mirror = 2 * center - i
            # Initialize radius based on mirrored value, but don't exceed right boundary
            P[i] = min(right_boundary - i, P[mirror])
        
        # Expand outward while characters match
        # We start from current radius and try to expand further
        while (i - P[i] - 1 >= 0 and 
               i + P[i] + 1 < n and 
               t[i - P[i] - 1] == t[i + P[i] + 1]):
            P[i] += 1
        
        # Update center and right boundary if we've expanded past current boundary
        if i + P[i] > right_boundary:
            center = i
            right_boundary = i + P[i]
        
        # Track the maximum radius found
        if P[i] > max_radius:
            max_center = i
            max_radius = P[i]
    
    # Extract the longest palindrome from original string
    # In transformed string, palindrome spans from (max_center - max_radius) to (max_center + max_radius)
    # Map back to original string indices
    start = (max_center - max_radius) // 2
    end = (max_center + max_radius) // 2
    return s[start:end]

# Example usage
print(longest_palindrome_manacher("babad"))    # Output: "bab" or "aba"
print(longest_palindrome_manacher("cbbd"))     # Output: "bb"
print(longest_palindrome_manacher("racecar"))  # Output: "racecar"
print(longest_palindrome_manacher("abba"))     # Output: "abba"
print(longest_palindrome_manacher("a" * 1000)) # Handles large uniform strings efficiently

Complexity Analysis

• Time Complexity: O(n) — The crucial observation: the while loop that expands palindromes only performs character comparisons that are "new" — that is, comparisons beyond the current rightmost boundary. Each successful comparison advances the right_boundary, and it can advance at most n times. Failed comparisons (at expansion boundaries) happen at most once per center. Thus total character comparisons are bounded by O(n).
• Space Complexity: O(n) — We store the transformed string of length 2n+1 and the radii array P of the same size. This is linear space, unavoidable if we want to return the actual substring.

Manacher's algorithm is the theoretical pinnacle for this problem. While rarely expected in standard interviews, it demonstrates deep algorithmic thinking and is worth knowing for competitions or situations where input strings are extremely large (millions of characters).

Step-by-step Trace of Manacher's Algorithm

Let's trace the algorithm on the input s = "abba" to solidify understanding:

Original string: "abba"
Transformed t:   "#a#b#b#a#" 
Indices:         0 1 2 3 4 5 6 7 8

Initial state: center=0, right_boundary=0, P = [0,0,0,0,0,0,0,0,0]

i=0: i is NOT < right_boundary (0 < 0 is false)
      Expand: nothing beyond bounds → P[0]=0
      i+P[i] = 0, not > right_boundary=0 → no update
      
i=1: i=1, right_boundary=0 → 1 < 0 false
      Expand around i=1 (character 'a'):
        t[0]='#' == t[2]='#'? YES → P[1]=1
        t[-1] out of bounds → stop
      P[1]=1, i+P[1]=2 > right_boundary=0 → update center=1, right_boundary=2
      max_radius=1, max_center=1

i=2: i=2, right_boundary=2 → 2 < 2 false (boundary is exclusive for initialization)
      Expand around i=2 (character '#'):
        t[1]='a' == t[3]='b'? NO → P[2]=0
      i+P[2]=2, not > right_boundary=2
      
i=3: i=3, right_boundary=2 → 3 < 2 false
      Expand around i=3 (character 'b'):
        t[2]='#' == t[4]='#'? YES → P[3]=1
        t[1]='a' == t[5]='b'? NO → stop
      P[3]=1, i+P[3]=4 > right_boundary=2 → update center=3, right_boundary=4
      
i=4: i=4, right_boundary=4 → 4 < 4 false
      Expand around i=4 ('#' between the two 'b's):
        t[3]='b' == t[5]='b'? YES → P[4]=1
        t[2]='#' == t[6]='#'? YES → P[4]=2
        t[1]='a' == t[7]='a'? YES → P[4]=3
        t[0]='#' == t[8]='#'? YES → P[4]=4
        t[-1] out of bounds → stop
      P[4]=4, i+P[4]=8 > right_boundary=4 → update center=4, right_boundary=8
      max_radius=4, max_center=4

...remaining indices processed similarly but don't surpass max_radius=4

Result mapping:
  start = (4 - 4) // 2 = 0
  end   = (4 + 4) // 2 = 4
  s[0:4] = "abba" ✓

This trace shows how the algorithm finds the full palindrome in just a few expansions, and how subsequent centers inside the large palindrome benefit from the mirroring optimization.

Comparing All Solutions

Here's a concise comparison table to guide your choice:

| Approach              | Time        | Space       | When to Use                          |
|-----------------------|-------------|-------------|--------------------------------------|
| Brute Force           | O(n³)       | O(1)        | Only for tiny strings (n < 50)       |
| Dynamic Programming   | O(n²)       | O(n²)       | Good for medium strings, educational |
| Expand Around Center  | O(n²)       | O(1)        | Best general-purpose solution        |
| Manacher's Algorithm  | O(n)        | O(n)        | Production with large n, competitions|

Best Practices and Common Pitfalls

1. Handle Edge Cases Explicitly

Always check for empty string and single-character inputs at the start of your function. A zero-length string should return "", and a single character should return itself. These checks prevent index-out-of-bounds errors and make your code robust.

2. Be Mindful of Python String Slicing Costs

In the brute force approach, creating substrings via s[i:j+1] allocates new memory. For palindrome checking, prefer two-pointer comparison over slicing when performance matters — it avoids allocation and runs faster in practice, even though asymptotic complexity remains the same.

3. Use the Expand-Around-Center as Your Default

For interview settings, the expand-around-center approach hits the right balance: it's easy to explain, easy to code correctly under pressure, and achieves optimal quadratic time with constant space. Save Manacher's for when the interviewer explicitly asks for linear time or when dealing with extremely long strings.

4. Test with Diverse Inputs

Validate your implementation against these representative cases:

# Test suite for LPS solutions
test_cases = [
    ("", ""),                          # Empty string
    ("a", "a"),                        # Single character
    ("aa", "aa"),                      # Two identical characters
    ("ab", "a"),                       # No palindrome longer than 1
    ("babad", "bab"),                  # Multiple answers, any valid
    ("cbbd", "bb"),                    # Even-length palindrome
    ("racecar", "racecar"),            # Whole string is palindrome
    ("abcde", "a"),                    # All unique characters
    ("aaaaa", "aaaaa"),                # All same characters
    ("abacdfgdcaba", "aba"),           # Nested palindromes
]

5. Know the Manacher's Transformation Trick

The sentinel-based transformation ('#'.join) is the standard way to unify odd/even palindrome handling. An alternative uses sentinels like '^' at start and '$' at end to avoid boundary checks during expansion, but the simpler single-sentinel approach with explicit bounds checking in the while loop is more transparent and equally efficient.

6. Avoid Recomputing Lengths Unnecessarily

In the expand-around-center implementation, compute palindrome length from the final left and right pointers after expansion exits: length = right - left - 1. This is O(1) and avoids slicing the string just to measure length.

Conclusion

The Longest Palindromic Substring problem serves as a masterclass in algorithmic optimization. Starting from the naive O(n³) brute force, we progressed through dynamic programming's O(n²) time with cached subproblems, arrived at the elegant O(n²) time / O(1) space center-expansion method, and finally explored Manacher's ingenious O(n) linear-time algorithm. Each solution illuminates a different algorithmic paradigm — exhaustive search, memoization, two-pointer expansion, and symmetry-based optimization — that you'll encounter repeatedly throughout your software engineering career. For day-to-day coding and interviews, the expand-around-center approach is your reliable workhorse; for pushing the boundaries of performance, Manacher's algorithm stands ready. Armed with this knowledge, you can now tackle palindrome problems with confidence and adapt these patterns to related challenges in string processing, computational biology, and beyond.