Longest palindromic substring
Given a string s, return its longest substring (contiguous) that reads the same forwards and
backwards. If several have the maximum length, return the one that starts earliest.
Examples
| Input | Output | Why |
|---|---|---|
s = "babad" | "bab" | "aba" is as long but starts later. |
s = "cbbd" | "bb" | An even-length palindrome. |
s = "ac" | "a" | Single characters are palindromes; "a" comes first. |
Constraints
- 1 ≤ s.length ≤ 1000
- Letters and digits
Hints
Hint 1
Every palindrome is centred on a character (odd length) or between two characters (even length).
Hint 2
From each of the 2n − 1 centres, expand while the characters on both sides match.
Hint 3
Replace the best only when strictly longer, scanning centres from left to right, to keep the earliest on ties.
Where people lose marks
- Expanding only around characters, which misses even-length palindromes such as "bb".
- Off-by-one in the final slice after the expansion overshoots by one on each side.
- Replacing on equal length, which reports the last palindrome instead of the first.
Dry run on "babad"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9sb0centrea1b2a3d4
Centre at 0: expands to "b" (length 1).
-
Step 2 / 9sb0centrea1b2a3d4
Centre between 0 and 1: expands to "" (length 0).
-
Step 3 / 9sb0a1centreb2a3d4
Centre at 1: expands to "bab" (length 3). New best.
-
Step 4 / 9sb0a1centreb2a3d4
Centre between 1 and 2: expands to "" (length 0).
-
Step 5 / 9sb0a1b2centrea3d4
Centre at 2: expands to "aba" (length 3).
-
Step 6 / 9sb0a1b2centrea3d4
Centre between 2 and 3: expands to "" (length 0).
-
Step 7 / 9sb0a1b2a3centred4
Centre at 3: expands to "a" (length 1).
-
Step 8 / 9sb0a1b2a3centred4
Centre between 3 and 4: expands to "" (length 0).
-
Step 9 / 9sb0a1b2a3d4centre
Centre at 4: expands to "d" (length 1). The answer is "bab".
How to think about it
A palindrome with matching ends around a palindromic middle is again a palindrome, which is the recurrence of the DP
table pal[i][j] = s[i] = s[j] and pal[i + 1][j − 1]. Expanding around centres uses the same fact without the
table: from each centre (a character, or the gap between two), grow outwards while the two new ends match. The longest
expansion found is the answer. Scanning centres left to right and replacing only on a strictly longer palindrome keeps
the earliest one among equals.
Complexity. Time O(n²) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def longest_palindrome(s):
best_lo, best_hi = 0, 1 # best palindrome is s[best_lo:best_hi]
for centre in range(2 * len(s) - 1): # characters and the gaps between them
lo, hi = centre // 2, (centre + 1) // 2
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo -= 1
hi += 1
if hi - lo - 1 > best_hi - best_lo: # strictly longer keeps the earliest
best_lo, best_hi = lo + 1, hi
return s[best_lo:best_hi]#include <string>
std::string solve(std::string s) {
int bestLo = 0, bestHi = 1, n = s.size();
for (int centre = 0; centre < 2 * n - 1; ++centre) {
int lo = centre / 2, hi = (centre + 1) / 2;
while (lo >= 0 && hi < n && s[lo] == s[hi]) { --lo; ++hi; }
if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; } // strictly longer
}
return s.substr(bestLo, bestHi - bestLo);
}class Solution {
public String longestPalindrome(String s) {
int bestLo = 0, bestHi = 1, n = s.length();
for (int centre = 0; centre < 2 * n - 1; centre++) {
int lo = centre / 2, hi = (centre + 1) / 2;
while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) { lo--; hi++; }
if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; } // strictly longer
}
return s.substring(bestLo, bestHi);
}
}function longestPalindrome(s) {
let bestLo = 0, bestHi = 1;
for (let centre = 0; centre < 2 * s.length - 1; centre++) {
let lo = centre >> 1, hi = (centre + 1) >> 1;
while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; } // strictly longer
}
return s.slice(bestLo, bestHi);
}fn solve(s: &str) -> String {
let c: Vec<u8> = s.bytes().collect();
let n = c.len() as i64;
let (mut best_lo, mut best_hi) = (0i64, 1i64);
for centre in 0..2 * n - 1 {
let (mut lo, mut hi) = (centre / 2, (centre + 1) / 2);
while lo >= 0 && hi < n && c[lo as usize] == c[hi as usize] {
lo -= 1;
hi += 1;
}
if hi - lo - 1 > best_hi - best_lo { // strictly longer
best_lo = lo + 1;
best_hi = hi;
}
}
s[best_lo as usize..best_hi as usize].to_string()
}import Data.List (foldl')
solve :: String -> String
solve s = take (hi - lo) (drop lo s)
where
n = length s
at i = s !! i
-- the widest palindrome around each centre, as (start, end)
expand l h | l >= 0 && h < n && at l == at h = expand (l - 1) (h + 1)
| otherwise = (l + 1, h)
spans = [expand (c `div` 2) ((c + 1) `div` 2) | c <- [0 .. 2 * n - 2]]
(lo, hi) = foldl' (\b@(bl, bh) x@(xl, xh) -> if xh - xl > bh - bl then x else b) (0, 1) spansVariants to try
- Count all palindromic substrings (each successful expansion step is one).
- Manacher's algorithm in O(n).
- The shortest palindrome formed by adding characters in front of s.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.