5. Longest Palindromic Substring - Explanation

Description

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Example 1:

Input: s = "ababd"

Output: "bab"

Explanation: Both "aba" and "bab" are valid answers.

Example 2:

Input: s = "abbc"

Output: "bb"

Constraints:

1 <= s.length <= 1000
s contains only digits and English letters.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n^2) time and O(1) space, where n is the length of the given string.

Hint 1

A brute-force solution would be to check if every substring is a palindrome and return the maximum length among all the palindromic substring lengths. This would be an O(n^3) time solution. Can you think of a better way? Perhaps you should consider thinking in terms of the center of a palindrome.

Hint 2

Iterate over the string with index i and treat the current character as the center. For this character, try to extend outward to the left and right simultaneously, but only if both characters are equal. Update the result variable accordingly. How would you implement this? Can you consider both cases: even-length and odd-length palindromes?

Hint 3

Maintain two variables, resLen and res, which denote the length of the longest palindrome and the start index of that palindrome, respectively. At each index, you can create an odd-length palindrome starting at that index extending outward from both its left and right indices, i.e., i - 1 and i + 1. How can you find the even-length palindrome for this index?

Hint 4

For an even-length palindrome, consider expanding from indices i and i + 1. This two-pointer approach, extending from the center of the palindrome, will help find all palindromic substrings in the given string. Update the two result variables and return the substring starting at res with a length of resLen.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A palindrome reads the same forward and backward.
The simplest idea is to try every possible substring and check whether it is a palindrome, then keep the longest one found.

For each pair (i, j):

Assume s[i:j] is a candidate substring
Use two pointers (l and r) to check if it’s a palindrome
If valid and longer than the current answer, update the result

This approach is straightforward but inefficient.

Algorithm

Initialize an empty result string and length 0.
For every start index i:
- For every end index j ≥ i:
  - Check if substring s[i..j] is a palindrome using two pointers.
  - If it is a palindrome and longer than the current best:
    - Update the result.
Return the longest palindrome found.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res, resLen = "", 0

        for i in range(len(s)):
            for j in range(i, len(s)):
                l, r = i, j
                while l < r and s[l] == s[r]:
                    l += 1
                    r -= 1

                if l >= r and resLen < (j - i + 1):
                    res = s[i : j + 1]
                    resLen = j - i + 1
        return res

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n)$

2. Dynamic Programming

Intuition

Instead of re-checking the same substrings again and again, we remember whether a substring is a palindrome.

Let:

dp[i][j] = true if the substring s[i..j] is a palindrome.

A substring s[i..j] is a palindrome when:

The end characters match: s[i] == s[j]
And the inside part is also a palindrome: dp[i+1][j-1]
- Special small cases: if the length is 1, 2, or 3 (j - i <= 2), then matching ends is enough because the middle is empty or a single char.

We fill dp from bottom to top (i from n-1 down to 0) so that when we compute dp[i][j], the value dp[i+1][j-1] is already known.

While filling, we keep track of the best (longest) palindrome seen so far.

Algorithm

Let n = len(s). Create a 2D table dp[n][n] initialized to false.
Keep resIdx = 0 and resLen = 0 for the best answer.
For i from n-1 down to 0:
- For j from i up to n-1:
  - If s[i] == s[j] and (j - i <= 2 OR dp[i+1][j-1] is true):
    - Mark dp[i][j] = true
    - If (j - i + 1) is bigger than resLen, update resIdx and resLen.
Return s[resIdx : resIdx + resLen].

class Solution:
    def longestPalindrome(self, s: str) -> str:
        resIdx, resLen = 0, 0
        n = len(s)

        dp = [[False] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if resLen < (j - i + 1):
                        resIdx = i
                        resLen = j - i + 1

        return s[resIdx : resIdx + resLen]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Two Pointers

Intuition

A palindrome expands symmetrically from its center.

Every palindrome has one of two centers:

Odd length → a single character center (e.g. "racecar")
Even length → between two characters (e.g. "abba")

So instead of checking all substrings, we:

Treat every index as a possible center
Expand left and right while characters match
Track the longest palindrome found during expansion

This avoids extra space and redundant checks.

Algorithm

Initialize:
- resIdx = 0 → starting index of best palindrome
- resLen = 0 → length of best palindrome
For each index i in the string:
- Odd-length palindrome
  - Set l = i, r = i
  - Expand while l >= 0, r < n, and s[l] == s[r]
- Even-length palindrome
  - Set l = i, r = i + 1
  - Expand while l >= 0, r < n, and s[l] == s[r]
- During each expansion, update resIdx and resLen if a longer palindrome is found
Return substring s[resIdx : resIdx + resLen]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        resIdx = 0
        resLen = 0

        for i in range(len(s)):
            # odd length
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    resIdx = l
                    resLen = r - l + 1
                l -= 1
                r += 1

            # even length
            l, r = i, i + 1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    resIdx = l
                    resLen = r - l + 1
                l -= 1
                r += 1

        return s[resIdx : resIdx + resLen]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output string.

4. Manacher's Algorithm

Intuition

Manacher’s Algorithm is an optimized way to find the longest palindromic substring in linear time.

The key ideas are:

Unify odd and even length palindromes by inserting a special character (like #) between characters.
- Example: "abba" → "#a#b#b#a#"
Use previous palindrome information to avoid re-checking characters.
Maintain a current rightmost palindrome and mirror indices to reuse results.

Instead of expanding from every center independently, Manacher’s algorithm reuses symmetry, making it much faster than the two-pointer approach.

Algorithm

Transform the string
- Insert # between characters and at both ends to handle odd/even palindromes uniformly.
Create an array p[]
- p[i] = radius of palindrome centered at index i in the transformed string.
Maintain two pointers:
- center → center of the current rightmost palindrome
- right → right boundary of that palindrome
For each index i:
- If i is inside the current palindrome:
  - Initialize p[i] using its mirror around center
- Expand around i while characters match
- If the palindrome expands beyond right, update center and right
After processing:
- Find the index with the maximum value in p
- Convert that position back to the original string indices
Return the longest palindromic substring

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def manacher(s):
            t = '#' + '#'.join(s) + '#'
            n = len(t)
            p = [0] * n
            l, r = 0, 0
            for i in range(n):
                p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
                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] > r:
                    l, r = i - p[i], i + p[i]
            return p

        p = manacher(s)
        resLen, center_idx = max((v, i) for i, v in enumerate(p))
        resIdx = (center_idx - resLen) // 2
        return s[resIdx : resIdx + resLen]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$