LeetCode 5 - Longest Palindromic Substring

The problem asks us to find the longest substring of a given string that is also a palindrome. A palindrome is a sequence that reads the same forward and backward. The substring must be contiguous, which means the characters must appear next to each other in the original string.

leetcodemediumtwo-pointersstringdynamic-programming

LeetCode Problem 5

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Dynamic Programming

Solution

Longest Palindromic Substring

The problem asks us to find the longest substring of a given string that is also a palindrome. A palindrome is a sequence that reads the same forward and backward. The substring must be contiguous, which means the characters must appear next to each other in the original string.

For example, in the string "babad", the substrings "bab" and "aba" are both palindromes of length 3, so either one is a valid answer. In the string "cbbd", the longest palindromic substring is "bb".

The input is a single string s, and the output is another string representing the longest palindromic substring found inside s.

The constraints are important:

  • The string length is between 1 and 1000.
  • The string contains only digits and English letters.

A maximum length of 1000 means that an extremely slow solution, such as checking every possible substring and verifying each one independently, may still work in some languages but is not ideal. We should aim for something more efficient.

Several edge cases are important:

  • A string with only one character, such as "a", is already a palindrome.
  • A string where every character is the same, such as "aaaa", should return the entire string.
  • A string with no repeated characters, such as "abcde", should return any single character.
  • Even-length palindromes, such as "abba", need special handling because their center lies between two characters.
  • Odd-length palindromes, such as "racecar", have a single center character.

Approaches

Brute Force Approach

The brute force solution generates every possible substring and checks whether each substring is a palindrome.

A string of length n has approximately n² substrings. For every substring, we can check whether it is a palindrome by comparing characters from both ends inward. That palindrome check itself takes O(n) time in the worst case.

This gives an overall complexity of O(n³).

The brute force method is correct because it exhaustively examines every possible substring and keeps track of the longest valid palindrome found. However, it becomes inefficient as the input size grows.

Optimal Approach, Expand Around Center

The key observation is that every palindrome has a center.

For odd-length palindromes, the center is a single character:

racecar
   ^

For even-length palindromes, the center lies between two characters:

abba
 ^^

Instead of checking every substring independently, we can expand outward from every possible center and stop as soon as the characters no longer match.

Since there are n possible odd centers and n - 1 possible even centers, we perform at most 2n - 1 expansions. Each expansion can take up to O(n) time in the worst case, giving an overall complexity of O(n²).

This is significantly faster than the brute force solution and works comfortably within the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Generates every substring and checks each palindrome individually
Optimal O(n²) O(1) Expands outward from each possible palindrome center

Algorithm Walkthrough

Expand Around Center Visualization

The central idea of the algorithm is repeatedly expanding outward while characters remain equal.

For an odd-length palindrome:

$f(x)=x$ .graphable-function-chartjs { position: relative; overflow: hidden; touch-action: none; }

    .graphable-function-chartjs-tooltip {
      position: absolute;
      z-index: 1;
      border-radius: 9px;
      background: rgb(0 0 0 / 90%);
      color: white;
      font-size: 11px;
      font-weight: 600;
      line-height: 14px;
      padding: 6px 12px;
      text-align: center;
      white-space: nowrap;
      pointer-events: none;
    }

    .graphable-function-chartjs-guide {
      position: absolute;
      top: 0;
      bottom: 0;
      border-left: 1px dashed var(--border-heavy);
      pointer-events: none;
    }

    .graphable-function-chartjs-hover-point {
      position: absolute;
      width: 8px;
      height: 8px;
      margin-left: -4px;
      margin-top: -4px;
      border: 1.5px solid white;
      border-radius: 9999px;
      background: black;
      pointer-events: none;
    }

    .graphable-function-chartjs-reset {
      position: absolute;
      left: 12px;
      bottom: 12px;
      display: inline-flex;
      align-items: center;
      justify-content: center;
      z-index: 2;
      width: 32px;
      height: 32px;
      border: 1px solid var(--border-light);
      border-radius: 9999px;
      background: var(--bg-primary);
      color: var(--text-primary);
      box-shadow: 0 2px 8px rgb(0 0 0 / 8%);
      padding: 0;
      transition: opacity 160ms ease, transform 160ms ease;
    }

Conceptually:

babad
  ^
 expand outward

For an even-length palindrome:

cbbd
 ^^
 expand outward

Step-by-Step Algorithm

  1. Initialize variables to track the best palindrome found so far.

We store the starting index and ending index of the longest palindrome discovered during processing. 2. Iterate through every index in the string.

Every character can act as the center of an odd-length palindrome. Additionally, every gap between adjacent characters can act as the center of an even-length palindrome. 3. Expand around an odd-length center.

Start with both pointers at the same index. While the left and right characters match and remain within bounds, continue expanding outward. 4. Expand around an even-length center.

Start with the left pointer at the current index and the right pointer at the next index. Again, continue expanding while the characters match. 5. Compare the discovered palindrome length with the current best.

If the new palindrome is longer, update the stored boundaries. 6. Continue until all centers have been processed.

Once every center has been explored, the stored substring boundaries represent the longest palindrome. 7. Return the substring using the saved indices.

Why It Works

Every palindrome must have a center. By expanding outward from every possible center, the algorithm guarantees that every valid palindrome in the string will eventually be considered. Since we always keep track of the longest palindrome found so far, the final result must be the longest palindromic substring.

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s

        start = 0
        end = 0

        def expand(left: int, right: int) -> tuple[int, 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)):
            # Odd-length palindrome
            left1, right1 = expand(i, i)

            # Even-length palindrome
            left2, right2 = expand(i, i + 1)

            if right1 - left1 > end - start:
                start, end = left1, right1

            if right2 - left2 > end - start:
                start, end = left2, right2

        return s[start:end + 1]

The implementation begins with a small optimization. If the string length is less than 2, the string itself is already the longest palindrome.

The expand helper function performs the core logic. It receives two indices representing the center of a potential palindrome. While the characters on both sides match, it expands outward.

When the loop stops, the pointers have already moved one step too far, so the function returns left + 1 and right - 1 to recover the valid palindrome boundaries.

Inside the main loop, we process two cases for every index:

  • Odd-length palindromes using (i, i)
  • Even-length palindromes using (i, i + 1)

After each expansion, we compare the resulting palindrome length against the current best palindrome. If the new palindrome is longer, we update the stored indices.

Finally, we return the substring using Python slicing.

Go Solution

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }

    start := 0
    end := 0

    expand := func(left int, right int) (int, int) {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }

        return left + 1, right - 1
    }

    for i := 0; i < len(s); i++ {
        // Odd-length palindrome
        left1, right1 := expand(i, i)

        // Even-length palindrome
        left2, right2 := expand(i, i+1)

        if right1-left1 > end-start {
            start = left1
            end = right1
        }

        if right2-left2 > end-start {
            start = left2
            end = right2
        }
    }

    return s[start : end+1]
}

The Go implementation closely mirrors the Python solution. One important difference is string slicing syntax. In Go, the substring is returned using s[start : end+1].

Go strings are immutable byte slices, so indexing operates directly on bytes. Since the problem guarantees only English letters and digits, byte indexing is safe here. If Unicode characters were allowed, rune conversion would be necessary.

Worked Examples

Example 1

Input:

s = "babad"

We iterate through every index and expand around both odd and even centers.

Index Odd Expansion Even Expansion Best So Far
0 "b" "" "b"
1 "bab" "" "bab"
2 "aba" "" "bab" or "aba"
3 "a" "" "bab"
4 "d" "" "bab"

Detailed expansion at index 1:

Initial:
b a b a d
  ^

Expand:
b a b a d
^   ^

Characters match:
'b' == 'b'

Next expansion goes out of bounds, stop.

Result:

"bab"

Example 2

Input:

s = "cbbd"
Index Odd Expansion Even Expansion Best So Far
0 "c" "" "c"
1 "b" "bb" "bb"
2 "b" "" "bb"
3 "d" "" "bb"

Detailed even expansion at index 1:

c b b d
  ^ ^

Characters match:
'b' == 'b'

Expand outward:
left = 0
right = 3

'c' != 'd'
Stop.

Result:

"bb"

Complexity Analysis

Measure Complexity Explanation
Time O(n²) There are O(n) centers, each expansion may scan O(n) characters
Space O(1) Only a few pointer variables are used

The algorithm processes every possible palindrome center. In the worst case, such as "aaaaaa", each expansion can traverse much of the string, producing quadratic time complexity. However, no additional data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.longestPalindrome("babad") in ["bab", "aba"]  # Odd-length palindrome
assert solution.longestPalindrome("cbbd") == "bb"  # Even-length palindrome
assert solution.longestPalindrome("a") == "a"  # Single character
assert solution.longestPalindrome("ac") in ["a", "c"]  # No palindrome longer than 1
assert solution.longestPalindrome("racecar") == "racecar"  # Entire string palindrome
assert solution.longestPalindrome("aaaa") == "aaaa"  # All identical characters
assert solution.longestPalindrome("abcda") in ["a", "b", "c", "d"]  # Multiple single-char answers
assert solution.longestPalindrome("forgeeksskeegfor") == "geeksskeeg"  # Large even palindrome
assert solution.longestPalindrome("abccba") == "abccba"  # Full even palindrome
assert solution.longestPalindrome("bananas") == "anana"  # Overlapping palindromes
Test Why
"babad" Verifies odd-length palindrome detection
"cbbd" Verifies even-length palindrome detection
"a" Tests minimum input size
"ac" Ensures single-character fallback works
"racecar" Confirms full-string palindrome handling
"aaaa" Tests repeated-character expansion
"abcda" Handles absence of longer palindromes
"forgeeksskeegfor" Tests large centered even palindrome
"abccba" Verifies complete even palindrome recognition
"bananas" Tests overlapping palindrome handling

Edge Cases

Single Character String

A string containing only one character is trivially a palindrome. Naive implementations sometimes fail because they assume at least two characters exist for expansion. This implementation handles the case immediately with:

if len(s) < 2:
    return s

Even-Length Palindromes

Many incorrect solutions only expand around a single character center, which misses cases like "abba" or "cbbd".

This implementation explicitly checks both:

expand(i, i)
expand(i, i + 1)

The second expansion correctly handles centers located between characters.

Strings With Repeated Characters

Inputs such as "aaaaaa" can cause repeated expansions over many identical characters. Some implementations accidentally terminate too early or fail to update the longest palindrome correctly.

Because this solution expands fully while characters match and always compares lengths before updating the result, it correctly returns the entire string.

No Long Palindrome Exists

For strings like "abcdef", every palindrome has length 1. Some implementations incorrectly return an empty string if no larger palindrome is found.

This solution initializes the result boundaries to the first character, ensuring at least one valid palindrome always exists.