Solving LeetCode Problem #5: Longest Palindromic Substring

LeetCode Problem #5: Longest Palindromic Substring

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

Example

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Approach 1: Expand Around Center

Concept

Every palindrome expands symmetrically from its center. Given a string of length n, there are 2n-1 possible centers (each character and the gaps between them). We expand from each center to determine the longest palindrome.

Implementation

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    start, end = 0, 0

    def expand_around_center(left: int, right: int):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        l1, r1 = expand_around_center(i, i)
        l2, r2 = expand_around_center(i, i + 1)

        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end+1]

Complexity Analysis

Time Complexity: O(n^2) in the worst case, since we expand from each center.
Space Complexity: O(1), as we only use pointers.

Approach 2: Dynamic Programming

Concept

We define dp[i][j] as True if s[i:j+1] is a palindrome. The recurrence relation is:

    dp[i][j] = True if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1])

Implementation

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

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

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

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if length > max_length:
                    start, max_length = i, length

    return s[start:start + max_length]

Complexity Analysis

Time Complexity: O(n^2), due to filling the DP table.
Space Complexity: O(n^2), for storing the table.

Approach 3: Manacher's Algorithm (Optimized to O(n))

Concept

This algorithm transforms the string with inserted delimiters (#) and uses a center-expansion technique while tracking the longest palindrome with an auxiliary array p.

Implementation

def longest_palindrome(s: str) -> str:
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n
    center, right = 0, 0
    max_center, max_len = 0, 0

    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])

        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]

        if p[i] > max_len:
            max_center, max_len = i, p[i]

    start = (max_center - max_len) // 2
    return s[start:start + max_len]

Complexity Analysis

Time Complexity: O(n), since each character is visited at most twice.
Space Complexity: O(n), for storing transformed string and auxiliary array.

Conclusion

Approach	Time Complexity	Space Complexity	Best Case
Expand Around Center	`O(n^2)`	`O(1)`	Simple and effective for small strings
Dynamic Programming	`O(n^2)`	`O(n^2)`	Useful for problems that require subproblem tracking
Manacher’s Algorithm	`O(n)`	`O(n)`	Best for large inputs

For competitive programming, Manacher's Algorithm is the optimal choice, but for readability and simplicity, Expand Around Center works well for most cases.

I build and scale reliable production systems. Open to full-time and freelance work with U.S.-based teams that value ownership and execution.

Got something in mind?

Book a Discovery Call