March 24
Longest Palindromic Substring
How to notice that every palindrome has a center and use that to avoid a heavier dynamic programming solution than necessary.
Strings and Expansion Intermediate 22 min TypeScript
Given a string s, return the longest palindromic substring.
In the SeniorPath playground, if multiple answers have the same length, return the one that appears first in the string.
Example:
Input: s = "babad"
Output: "bab"
What to notice before coding
- A palindromic substring is still mirrored comparison.
- The center can be one letter or the gap between two letters.
- The playground needs deterministic tie-breaking when multiple answers are valid.
Common mistakes
- considering only odd centers and missing cases like `"bb"`
- jumping to 2D DP before checking the simpler approach
Step 1 - Separate substring from subsequence
The problem asks for a substring.
That means:
- the characters must stay contiguous
So you are not allowed to skip letters in the middle.
Step 2 - Write the most direct baseline
The natural baseline is:
- test every possible substring
- check whether it is a palindrome
- keep the longest one
It works.
But it repeats too much work.
Step 3 - Ask what every palindrome has in common
Every palindrome grows from a center.
That center can be:
- a single letter, as in
"aba" - the gap between two letters, as in
"abba"
If you can expand from that center, you do not need to enumerate everything from scratch.
Step 4 - Turn that into expansion with two pointers
For each position in the string:
- try odd center:
(i, i) - try even center:
(i, i + 1)
Keep expanding while both sides stay equal.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function longestPalindrome(s: string): string {
// your solution here
return ""
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n^2)
Space: O(1)
Solution 1 - Test every substring O(n²)
Good baseline because it makes the high cost obvious.
function isPalindrome(candidate: string): boolean {
let left = 0
let right = candidate.length - 1
while (left < right) {
if (candidate[left] !== candidate[right]) {
return false
}
left += 1
right -= 1
}
return true
}
export function longestPalindrome(s: string): string {
let best = s[0] ?? ""
for (let start = 0; start < s.length; start += 1) {
for (let end = start; end < s.length; end += 1) {
const candidate = s.slice(start, end + 1)
if (candidate.length > best.length && isPalindrome(candidate)) {
best = candidate
}
}
}
return best
}It works, but it compares too many substrings.
Solution 2 - Expand around the center with two pointers
Now you use the structure of palindromes instead of guessing all substrings blindly.
function expandAroundCenter(s: string, left: number, right: number): [number, number] {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left -= 1
right += 1
}
return [left + 1, right - 1]
}
export function longestPalindrome(s: string): string {
if (s.length <= 1) {
return s
}
let bestStart = 0
let bestEnd = 0
for (let index = 0; index < s.length; index += 1) {
const odd = expandAroundCenter(s, index, index)
const even = expandAroundCenter(s, index, index + 1)
for (const [start, end] of [odd, even]) {
const candidateLength = end - start + 1
const bestLength = bestEnd - bestStart + 1
if (candidateLength > bestLength || (candidateLength === bestLength && start < bestStart)) {
bestStart = start
bestEnd = end
}
}
}
return s.slice(bestStart, bestEnd + 1)
}The strong insight here is choosing the right property: palindromes do not need 2D DP to exist. They only need a center.
What to say in the interview
A strong short explanation would be:
The baseline tests every substring and checks whether it is a palindrome, which is too expensive. The stronger version uses the fact that every palindrome has a center. For each index I expand around it with two pointers, both for the odd and even case, and update the best answer.
That shows that you:
- understood the structure of the problem
- chose the simpler approach before the heavier one
- explain the optimization as a reason, not just a result
When this pattern shows up again
This pattern comes back when you need to:
- compare mirrored characters around a point
- work with contiguous string regions
- prefer a structural solution over heavier dynamic programming
The point is not memorizing “expand from center.”
The point is noticing when the center is the most useful property.