5. Longest Palindromic Substring
Model: qwen3.5:9b
Topics: String,Dynamic Programming
FAANG asked: 1
Acceptance rate: 30.6%
Problem Breakdown
We are given a string s and need to find the longest substring that reads the same forwards and backwards.
- Input: A single string
s. Constraints indicate length is between 1 and 1000. Characters include digits, lowercase, and uppercase English letters. This implies case sensitivity (e.g., “AbA” != “aba”). - Output: The substring itself as a string. If multiple substrings have the same maximum length, returning any one of them is acceptable per standard LeetCode conventions for this problem.
- Edge Cases to consider:
- Single character strings (length 1).
- Strings with no palindromes longer than 1 char (e.g., “ac”).
- All characters are the same (“aaaaa”), where we must return the whole string.
Intuition
First, I’d consider a brute-force approach: iterate through every possible substring and check if it’s a palindrome. There are substrings, and checking each takes time, resulting in . Given s.length up to 1000, this is roughly operations worst-case, which might TLE (Time Limit Exceeded).
Next, I could use Dynamic Programming. We define a boolean table where dp[i][j] indicates if the substring from index i to j is a palindrome. This reduces time complexity to but requires an space matrix ( booleans), which is acceptable memory-wise but not optimal for auxiliary space.
A more efficient insight comes from the definition of a palindrome: it expands symmetrically around its center line or character. Since every substring has exactly one “center” (either an index i for odd-length palindromes, or between indices i and i+1 for even-length ones), we can iterate through each possible center in the string and expand outwards as long as characters match. This approach achieves time complexity but uses only constant extra space ().
Approach
I will use the Expand Around Center technique:
- Initialize
startindex andmax_lento track the best palindrome found so far. - Iterate through each character in the string using an index
i. This represents a potential center for odd-length palindromes (centered ati). - For every
i, also consider the space betweeniandi+1as a center for even-length palindromes. - Create two helper calls or logic blocks: one expanding from
(left, right) = (i, i)and another from(i, i + 1). - Inside the expansion loop, while characters at
s[left]ands[right]match, incrementally expand outward (left--,right++). - Whenever a palindrome is found that is longer than our current maximum, update
startandmax_len. - Finally, return the substring using Python slicing:
s[start : start + max_len].
Complexity Analysis
- Time Complexity: . We have an outer loop running times (for each center). In the worst case (e.g., string of all ‘a’s), the inner expansion runs up to for every center. Total operations , which simplifies to quadratic time.
- Space Complexity: . We only use a few variables (
start,max_len, loop counters). The output string is not counted in auxiliary space complexity, but the input storage dominates memory usage here.
Solution
def longestPalindrome(s: str) -> str:
if len(s) < 2:
return s
start = 0
max_len = 1
def expand_around_center(left: int, right: int):
nonlocal start, max_len
# Expand while characters match and indices are within bounds
while left >= 0 and right < len(s) and s[left] == s[right]:
if (right - left + 1) > max_len:
start = left
max_len = right - left + 1
left -= 1
right += 1
# Iterate over each character as a center for odd-length palindromes
for i in range(len(s)):
expand_around_center(i, i) # Odd length (center at i)
# Even length (center between i and i+1)
if len(s) > 0:
expand_around_center(i, i + 1)
return s[start : start + max_len]
Edge Cases Handled
- Single Character: The loop runs once for
i=0, expansion finds length 1 immediately. Returns the string itself (handled by initial check or logic flow). - No Palindromes > 1 char: If input is “ac”, odd expansions find ‘a’ and ‘c’, even expansion fails at first step. Max len remains 1, returns first character found (“a”).
- All Same Characters: Expansion continues until bounds are hit for every center, correctly identifying the full string as longest palindrome.
- Case Sensitivity: The comparison
s[left] == s[right]is strict equality in Python, so “AbA” will not match if case differs (e.g., ‘a’ vs ‘A’).