What pattern does Longest Palindromic Substring use?

The Pattern: Two Pointers (Expand Around Center) The Heuristic: To find palindromes efficiently, treat each character and each gap between characters as a center and expand pointers outward symmetrically until the palindrome property breaks, thereby avoiding redundant substring checks.

Longest Palindromic Substring - LeetCode Solution

Q: What is the time complexity of Longest Palindromic Substring?

O(n^2). For each of the n indices, the algorithm expands outward at most n times in the worst case, resulting in O(n^2) total operations.

Problem

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

1 ≤ s.length ≤ 1000
s consists of ASCII characters

Example

Input: s = "babad"

Output: "bab"

The brute-force approach would check every substring to see if it is a palindrome, which is O(n^3) due to substring extraction and palindrome checks. Instead, the optimal strategy expands around potential palindrome centers. For example, at index 1 ('a'), the algorithm expands left and right to check for odd-length palindromes like 'bab'. Similarly, it checks even-length palindromes by expanding around pairs of characters. The critical moment is when the algorithm finds a palindrome longer than the current longest and updates the result accordingly. This approach reduces the complexity to O(n^2) by avoiding repeated substring checks and leveraging symmetry.

Approach

Straightforward Solution

Check every substring and verify if it is a palindrome by comparing characters from both ends. This brute-force approach is O(n^3) due to O(n^2) substrings and O(n) palindrome checks, which is inefficient for large inputs.

Core Observation

A palindrome reads the same forwards and backwards. Any palindrome can be expanded from its center. Since palindromes can be odd or even length, centers can be single characters or pairs of characters.

Path to Optimal

The key recognition signals are 'longest palindromic substring' and 'substring' (contiguous), which suggest expanding around centers. Instead of checking all substrings, the algorithm treats each index (and each pair of adjacent indices) as a potential palindrome center and expands outwards while characters match. This reduces redundant checks and leverages the palindrome's symmetric property.

Optimal Approach

Iterate through each index in the string, expanding around it to find the longest odd-length palindrome, then expand around the gap between this index and the next to find the longest even-length palindrome. Track the longest palindrome found and update the result accordingly. This approach runs in O(n^2) time and O(1) auxiliary space, which is optimal for this problem.

Time

O(n^2)

For each of the n indices, the algorithm expands outward at most n times in the worst case, resulting in O(n^2) total operations.

Space

O(1)

Only a few variables are used to track indices and the current longest palindrome; no additional data structures proportional to input size are needed.

Solution

1class Solution:
  def longestPalindrome(self, s: str) -> str:
      res = ""
      res_len = 0
5
      for i in range(len(s)):
          l, r = i, i
          while l >= 0 and r < len(s) and s[l] == s[r]:
              if (r - l + 1) > res_len:
                  res = s[l:r+1]
                  res_len = r - l + 1
              l -= 1
              r += 1
          
          l, r = i, i + 1
          while l >= 0 and r < len(s) and s[l] == s[r]:
              if (r - l + 1) > res_len:
                  res = s[l:r+1]
                  res_len = r - l + 1
              l -= 1
              r += 1
      
      return res

Step-by-Step Solution

1

Initialize Result Variables to Track Longest Palindrome

3res = ""
4res_len = 0

Objective

To prepare variables that store the longest palindrome substring found and its length.

Key Insight

Tracking the longest palindrome and its length allows the algorithm to update the result only when a longer palindrome is found during expansions. Initializing with empty string and zero length ensures correctness even for single-character inputs.

Interview Quick-Check

Core Logic

The variables `res` and `res_len` maintain the current longest palindrome substring and its length, enabling efficient updates.

State & Boundaries

Starting with an empty string and zero length handles edge cases where the input string length is 1.

2

Expand Around Single Character Centers to Find Odd-Length Palindromes

6for i in range(len(s)):
  l, r = i, i
  while l >= 0 and r < len(s) and s[l] == s[r]:
      if (r - l + 1) > res_len:
          res = s[l:r+1]
          res_len = r - l + 1
      l -= 1
      r += 1

Objective

To find the longest odd-length palindrome centered at each index by expanding pointers outward symmetrically.

Key Insight

Odd-length palindromes have a single center character. By initializing left and right pointers at the same index and expanding outward while characters match, the algorithm efficiently finds the longest palindrome centered at that character without checking all substrings explicitly.

Interview Quick-Check

Core Logic

Expanding pointers `l` and `r` outward while `s[l] == s[r]` captures the maximal odd-length palindrome centered at index `i`.

State & Boundaries

The expansion stops when pointers go out of bounds or characters differ, ensuring only valid palindromes are considered.

Common Pitfalls & Bugs

Forgetting to update the result when a longer palindrome is found leads to incorrect answers.

3

Expand Around Adjacent Character Pairs to Find Even-Length Palindromes

15l, r = i, i + 1
16while l >= 0 and r < len(s) and s[l] == s[r]:
  if (r - l + 1) > res_len:
      res = s[l:r+1]
      res_len = r - l + 1
  l -= 1
  r += 1

Objective

To find the longest even-length palindrome centered between each pair of adjacent characters by expanding pointers outward symmetrically.

Key Insight

Even-length palindromes have two center characters. By initializing left pointer at index `i` and right pointer at `i+1`, the algorithm expands outward while characters match, capturing all even-length palindromes efficiently without redundant checks.

Interview Quick-Check

Core Logic

Expanding pointers `l` and `r` outward from adjacent indices captures the maximal even-length palindrome centered between `i` and `i+1`.

State & Boundaries

Expansion halts when pointers go out of bounds or characters differ, ensuring correctness.

Common Pitfalls & Bugs

Neglecting even-length palindromes results in missing valid longer palindromes.

4

Return the Longest Palindromic Substring Found

23	`return res`

Objective

To output the longest palindrome substring after all expansions have been checked.

Key Insight

After iterating through all possible centers and updating the longest palindrome, returning the stored result provides the correct answer. This final step consolidates all previous computations.

Interview Quick-Check

Core Logic

Returning `res` outputs the longest palindrome substring found during the expansions.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

while l >= 0 and r < len(s) and s[l] == s[r]:

Expand pointers outward while within bounds and characters at pointers match.

Expanding outward symmetrically from the center is the core mechanism that efficiently finds palindromes without checking all substrings.

Line 16 Critical

while l >= 0 and r < len(s) and s[l] == s[r]:

Expand pointers outward while within bounds and characters at pointers match for even-length palindrome.

This expansion is critical to capture even-length palindromes, which would be missed if only single centers were considered.

Line 9 Core

if (r - l + 1) > res_len:

Check if the current palindrome length exceeds the longest found so far.

This condition ensures the algorithm only updates the result when a strictly longer palindrome is found, maintaining correctness.

Line 10 Core

res = s[l:r+1]

Update the result substring to the current longest palindrome.

Storing the substring immediately upon finding a longer palindrome ensures the final output is correct and up-to-date.

Line 17 Core

if (r - l + 1) > res_len:

Check if the current palindrome length exceeds the longest found so far.

Ensures the algorithm updates the result only when a longer palindrome is found, preserving correctness.

Line 18 Core

res = s[l:r+1]

Update the result substring to the current longest palindrome.

Capturing the substring immediately upon discovery guarantees the final output is the longest palindrome.

Line 7 Core

l, r = i, i

Set left and right pointers to the current index for odd-length palindrome expansion.

Initializing both pointers at the same index targets palindromes with a single center character.

Line 11 Core

res_len = r - l + 1

Update the length of the longest palindrome found.

Maintaining the length allows efficient comparisons in subsequent iterations without recomputing substring lengths.

Line 15 Core

l, r = i, i + 1

Set left pointer to current index and right pointer to the next index for even-length palindrome expansion.

Initializing pointers at adjacent indices targets palindromes with two center characters, covering even-length cases.

Line 19 Core

res_len = r - l + 1

Update the length of the longest palindrome found.

Maintaining the length allows efficient future comparisons without recomputing substring lengths.

Line 23 Core

return res

Return the longest palindromic substring found.

After all expansions, returning the stored result provides the correct longest palindrome substring.

Line 4 Standard

res_len = 0

Initialize the length of the longest palindrome to zero.

Tracking the length allows efficient comparison to update the longest palindrome only when a longer one is found.

Line 6 Standard

for i in range(len(s)):

Iterate through each character index in the string as a potential palindrome center.

Each index serves as a candidate center for odd-length palindromes, ensuring all possibilities are explored.

Line 12 Standard

l -= 1

Move the left pointer one step left to expand the palindrome.

Moving left pointer outward is essential to check the next potential palindrome boundary on the left side.

Line 13 Standard

r += 1

Move the right pointer one step right to expand the palindrome.

Moving right pointer outward complements the left pointer movement, maintaining symmetric expansion.

Line 20 Standard

l -= 1

Move the left pointer one step left to expand the palindrome.

Expanding the left boundary is necessary to check for larger palindromes.

Line 21 Standard

r += 1

Move the right pointer one step right to expand the palindrome.

Expanding the right boundary complements the left pointer movement, maintaining symmetry.

Line 3 Standard

res = ""

Initialize an empty string to store the longest palindrome found.

Starting with an empty string ensures the algorithm can update the result as soon as it finds any palindrome, including single characters.

Test Your Understanding

Why does expanding around centers guarantee finding all palindromic substrings without missing any?

Because every palindrome has a center (either a single character for odd-length or a pair for even-length), expanding around all possible centers ensures all palindromes are considered exactly once.

Don't just read it. Drill it.

Reconstruct Longest Palindromic Substring from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Palindromic Substring drill

or drill a free problem

1	`class Solution:`
2	`def longestPalindrome(self, s: str) -> str:`
3	`res = ""`
4	`res_len = 0`
5
6	`for i in range(len(s)):`
7	`l, r = i, i`
8	`while l >= 0 and r < len(s) and s[l] == s[r]:`
9	`if (r - l + 1) > res_len:`
10	`res = s[l:r+1]`
11	`res_len = r - l + 1`
12	`l -= 1`
13	`r += 1`
14
15	`l, r = i, i + 1`
16	`while l >= 0 and r < len(s) and s[l] == s[r]:`
17	`if (r - l + 1) > res_len:`
18	`res = s[l:r+1]`
19	`res_len = r - l + 1`
20	`l -= 1`
21	`r += 1`
22
23	`return res`

6	`for i in range(len(s)):`
7	`l, r = i, i`
8	`while l >= 0 and r < len(s) and s[l] == s[r]:`
9	`if (r - l + 1) > res_len:`
10	`res = s[l:r+1]`
11	`res_len = r - l + 1`
12	`l -= 1`
13	`r += 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Result Variables to Track Longest Palindrome

Expand Around Single Character Centers to Find Odd-Length Palindromes

Expand Around Adjacent Character Pairs to Find Even-Length Palindromes

Return the Longest Palindromic Substring Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.