LeetCode 5: Longest Palindromic Substring

Problem Statement

LeetCode 5, Longest Palindromic Substring, is a medium-level challenge where you find the longest substring in a string s that reads the same forward and backward (a palindrome). A substring is a continuous piece of the string, and the goal is to return the actual substring (not just its length) that’s the longest palindrome. The string can have letters or numbers, and there’s always at least one palindrome (a single letter).

Constraints

  • 1 <= s.length <= 1000: String length is between 1 and 1000.
  • s consists of lowercase or uppercase English letters, or digits.
  • At least one palindrome exists.

Example

Input: s = "babad"
Output: "bab"
Explanation: "bab" is a palindrome (b-a-b), length 3. "aba" also works, but we return one.

Input: s = "cbbd"
Output: "bb"
Explanation: "bb" is a palindrome (b-b), length 2.

Input: s = "a"
Output: "a"
Explanation: Single letter "a" is a palindrome, length 1.

Understanding the Problem

A palindrome is like a mirror: "racecar" reads the same both ways, but "race" doesn’t. We need the longest continuous chunk of s that’s a palindrome. For "babad", both "bab" and "aba" are palindromes of length 3, and we pick one. The string might have many palindromes, so we test systematically. We’ll explore two solutions:

  • Expand Around Center: Grow palindromes from each spot.
  • Dynamic Programming: Build a table of palindrome checks.

Solution 1: Expand Around Center

Explanation

This method treats each letter (or spot between letters) as the middle of a possible palindrome and expands outward to find the longest one. Palindromes can be odd-length (like "aba") or even-length (like "bb"), so we check both.

  1. Initialize Variables.
  • Keep track of the longest palindrome’s start and end positions.

2. Check Each Center.

  • For every position, expand around it for odd length (centered on a letter) and even length (between two letters).

3. Expand and Compare.

  • Grow the palindrome while letters match, updating the longest found.

4. Return Substring.

  • Use the start and end positions to grab the longest palindrome.

Step-by-Step Example

Example 1: s = "babad"

We have the string "babad" and want the longest palindrome.

  • Goal: Find the longest chunk that reads the same both ways.
  • Result for reference: "bab" or "aba" are both 3 letters long, we’ll get "bab".
  • Start: Set longest start at 0, length at 1 (single letter is a palindrome).
  • Step 1: Center at position 0 (b).
    • Odd: Just b, length 1.
    • Even (between 0 and 1): b and a don’t match, length 0.
    • Longest so far: "b", length 1.
  • Step 2: Center at position 1 (a).
    • Odd: Expand from a: b-a-b. Matches! Length 3.
    • Even (between 1 and 2): a and b don’t match, length 0.
    • Longest now: "bab", length 3.
  • Step 3: Center at position 2 (b).
    • Odd: Just b, length 1 (expand to a-b-a, works, length 3).
    • Even (between 2 and 3): b and a don’t match, length 0.
    • Longest stays "bab" (or updates to "aba"), length 3.
  • Step 4: Center at position 3 (a).
    • Odd: Just a, length 1.
    • Even (between 3 and 4): a and d don’t match, length 0.
    • Longest stays "bab", length 3.
  • Step 5: Center at position 4 (d).
    • Odd: Just d, length 1.
    • Even: No letter after, length 0.
    • Longest stays "bab", length 3.
  • Finish: Return "bab" (positions 0 to 2).
    • Length 3, a valid palindrome.

Example 2: s = "cbbd"

Now, the string is "cbbd".

  • Goal: Find the longest palindrome.
  • Result for reference: "bb" is 2 letters long.
  • Start: Longest starts as "c", length 1.
  • Step 1: Center at 0 (c).
    • Odd: Just c, length 1.
    • Even (0 to 1): c and b don’t match, length 0.
    • Longest: "c", length 1.
  • Step 2: Center at 1 (b).
    • Odd: Just b, length 1.
    • Even (1 to 2): b and b match! Length 2.
    • Longest: "bb", length 2.
  • Step 3: Center at 2 (b).
    • Odd: Just b, length 1.
    • Even (2 to 3): b and d don’t match, length 0.
    • Longest stays "bb", length 2.
  • Step 4: Center at 3 (d).
    • Odd: Just d, length 1.
    • Even: No next letter, length 0.
    • Longest stays "bb", length 2.
  • Finish: Return "bb" (positions 1 to 2).
    • Length 2, the longest palindrome.

Code

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

    start = 0
    max_length = 1

    def expand_around_center(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

    for i in range(len(s)):
        len1 = expand_around_center(i, i)  # Odd length
        len2 = expand_around_center(i, i + 1)  # Even length
        curr_max = max(len1, len2)
        if curr_max > max_length:
            max_length = curr_max
            start = i - (curr_max - 1) // 2

    return s[start:start + max_length]

Complexity

  • Time Complexity: O(n²) – Each center might expand to the full string.
  • Space Complexity: O(1) – Just a few variables.

Efficiency Notes

It’s straightforward and works well for medium-sized strings, but it’s not the fastest possible.

Solution 2: Dynamic Programming

Explanation

This method builds a table to mark which substrings are palindromes, starting small and growing bigger, then picks the longest one.

  1. Initialize Table.
  • Make a grid where dp[i][j] is True if substring from i to j is a palindrome.

2. Fill Table.

  • Start with single letters (always palindromes), then pairs, then longer stretches.

3. Track Longest.

  • Update start and length when finding longer palindromes.

4. Return Substring.

  • Use the longest palindrome’s start and length.

Step-by-Step Example

Example 1: s = "babad"

We have "babad" and want the longest palindrome.

  • Goal: Find the longest stretch that’s the same backward and forward.
  • Result for reference: "bab" or "aba", length 3, we’ll get "bab".
  • Start: Make a table, set longest to "b", length 1.
  • Step 1: Single letters (length 1).
    • All are palindromes: b, a, b, a, d. Table marks these True.
    • Longest: "b", length 1.
  • Step 2: Pairs (length 2).
    • Check ba, ab, ba, ad. None match, all False.
    • Longest stays "b", length 1.
  • Step 3: Length 3.
    • b-a-b: Ends match (b = b), middle a is True, so True. Length 3.
    • a-b-a: Ends match (a = a), middle b is True, so True. Length 3.
    • b-a-d: Ends don’t match, False.
    • Longest: "bab" (0 to 2), length 3.
  • Step 4: Length 4.
    • b-a-b-a: Ends don’t match (b ≠ a), False.
    • a-b-a-d: Ends don’t match, False.
    • Longest stays "bab".
  • Step 5: Length 5.
    • b-a-b-a-d: Ends don’t match, False.
    • Longest stays "bab".
  • Finish: Return "bab", length 3.

Example 2: s = "cbbd"

Now, the string is "cbbd".

  • Goal: Find the longest palindrome.
  • Result for reference: "bb", length 2.
  • Start: Table, longest "c", length 1.
  • Step 1: Singles.
    • c, b, b, d all True, length 1.
    • Longest: "c".
  • Step 2: Pairs.
    • c-b: False.
    • b-b: True, length 2.
    • b-d: False.
    • Longest: "bb" (1 to 2), length 2.
  • Step 3: Length 3.
    • c-b-b: Ends don’t match, False.
    • b-b-d: Ends don’t match, False.
    • Longest stays "bb".
  • Step 4: Length 4.
    • c-b-b-d: Ends don’t match, False.
    • Longest stays "bb".
  • Finish: Return "bb", length 2.

Code

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""

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

    # Single letters
    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 = i
            max_length = 2

    # Longer lengths
    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
                start = i
                max_length = length

    return s[start:start + max_length]

Complexity

  • Time Complexity: O(n²) – Filling the table takes n² steps.
  • Space Complexity: O(n²) – Table size is n by n.

Efficiency Notes

It’s reliable but uses more space than expanding around centers.

Additional Example

For s = "racecar":

  • Goal: Longest palindrome.
  • Reference: "racecar", length 7.
  • Expand method: Center at e, grows to "racecar".
  • DP: Table builds up to r-a-c-e-c-a-r, length 7.
  • Result: "racecar".

Edge Cases

  • Single Letter: s = "a" – Returns "a".
  • All Same: s = "aaa" – Returns "aaa".
  • Empty: s = "" – Returns "" (though not per constraints).

Final Thoughts

  • Expand Around Center: Fast and space-light, great for interviews.
  • Dynamic Programming: Solid and structured, good for learning tables.