These are the notes for DSA episode 72. Two kids on a long train ride invent a word game: find the longest palindrome hiding inside a word (in bananas it is anana), then cut a word into palindromes with the fewest cuts (banana → b | anana, one cut). For round one we check every substring (correct, then Time Limit Exceeded on 8,000 letters), find the key fact (a palindrome is a smaller palindrome with the same letter on each side), and grow from each of the 2n - 1 centres in O(n²) time and O(1) space. For round two we try every first piece (Time Limit Exceeded on 40 a's), then build a pal[i][j] table filled from the bottom row up and a pieces[i] DP over prefixes, word break's cousin. Then every partition by backtracking, and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| The train word game | In code |
|---|---|
| A word that reads the same backwards (level, noon, Malayalam) | a palindrome |
| A part of the word, no letters skipped | a substring s[i..j] |
| Round 1: the longest hidden palindrome | LeetCode 5 |
| Round 2: cut into palindromes, fewest cuts | LeetCode 132 |
| Writing down every way to cut | LeetCode 131 |
Every word, from zero
- Palindrome: a string equal to its reverse:
level,abba,a. Every single letter is one. - Substring: consecutive letters
s[i..j](both ends included in these notes). Not the same as a subsequence, where letters may be skipped. - Centre: the middle of a palindrome. Odd length: a letter (
le[v]el). Even length: the gap between two letters (ab|ba). - Expand around the centre: step one letter outwards on both sides while the two letters match.
- Partition: cutting a string into consecutive pieces;
kpieces needk - 1cuts. pal[i][j]: a table saying whethers[i..j]is a palindrome.pieces[i]: the fewest palindromes that the firstiletters can be cut into.- Backtracking: choose, recurse, undo (episode 31).
- Manacher's algorithm: an O(n) algorithm for the longest palindromic substring; rarely asked.
Problem 1: Longest Palindromic Substring (LeetCode 5)
Return the longest substring of s that is a palindrome. 1 ≤ n ≤ 1000 on LeetCode.
| s | Answer |
|---|---|
babad |
bab (aba is fine too) |
cbbd |
bb (even length) |
bananas |
anana |
a |
a |
ac |
a |
malayalam |
malayalam |
Obvious idea: check every substring
import java.util.*;
public class Main {
static String longest(String s) {
String best = "";
for (int i = 0; i < s.length(); i++)
for (int j = i; j < s.length(); j++)
if (isPal(s, i, j) && j - i + 1 > best.length())
best = s.substring(i, j + 1);
return best;
}
static boolean isPal(String s, int i, int j) {
while (i < j)
if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
public static void main(String[] args) {
System.out.println(longest("babad"));
System.out.println(longest("cbbd"));
System.out.println(longest("bananas"));
System.out.println(longest("a"));
System.out.println(longest("ac"));
System.out.println(longest("malayalam"));
}
}
bab
bb
anana
a
a
malayalam
Correct. Now 8,000 equal letters: about 32 million substrings, and each check walks to the middle.
import java.util.*;
public class Main {
static String longest(String s) {
String best = "";
for (int i = 0; i < s.length(); i++)
for (int j = i; j < s.length(); j++)
if (isPal(s, i, j) && j - i + 1 > best.length())
best = s.substring(i, j + 1);
return best;
}
static boolean isPal(String s, int i, int j) {
while (i < j)
if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
public static void main(String[] args) {
String s = "a".repeat(8000);
long t0 = System.nanoTime();
int len = longest(s).length();
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("8000 letters: " + len + ", " + ms + " ms");
}
}
Time Limit Exceeded (stopped after 25 s)
Why is it slow?
n² / 2substrings × up ton / 2comparisons = O(n³).- Checking
ananacompares the outeras, then thens, then the middle; checkingnancompares the samens and middle again. - Key fact: a palindrome is a smaller palindrome with the same letter added on each side (
anana=a+nan+a).
The key insight: grow from the centre
| Step | Rule |
|---|---|
| Centres | n letters (odd lengths) + n - 1 gaps (even lengths) = 2n - 1 |
| Grow | while s[lo] == s[hi]: lo--, hi++ |
| Stop | at the first mismatch: no bigger palindrome has this centre |
| Length | when the loop stops, lo and hi are one step outside: hi - lo - 1 |
| Start | c - (len - 1) / 2 |
By hand: bananas
| Centre | Steps | Palindrome |
|---|---|---|
letter 1 (a) |
b ≠ n: stop |
a (1) |
letter 2 (n) |
a = a, then b ≠ n |
ana (3) |
letter 3 (a) |
n = n, a = a, then b ≠ s |
anana (5) |
| gap 3-4 | a ≠ n |
(0) |
Solution in Java
import java.util.*;
public class Main {
static String longest(String s) {
int start = 0, len = 0;
for (int c = 0; c < s.length(); c++) {
int odd = grow(s, c, c), even = grow(s, c, c + 1);
int m = Math.max(odd, even);
if (m > len) { len = m; start = c - (m - 1) / 2; }
}
return s.substring(start, start + len);
}
static int grow(String s, int lo, int hi) {
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
return hi - lo - 1;
}
public static void main(String[] args) {
System.out.println(longest("babad"));
System.out.println(longest("cbbd"));
System.out.println(longest("bananas"));
System.out.println(longest("a"));
System.out.println(longest("ac"));
System.out.println(longest("malayalam"));
}
}
bab
bb
anana
a
a
malayalam
The 8,000 letters that timed out, and a 16,007-letter string that is one big palindrome:
import java.util.*;
public class Main {
static String longest(String s) {
int start = 0, len = 0;
for (int c = 0; c < s.length(); c++) {
int odd = grow(s, c, c), even = grow(s, c, c + 1);
int m = Math.max(odd, even);
if (m > len) { len = m; start = c - (m - 1) / 2; }
}
return s.substring(start, start + len);
}
static int grow(String s, int lo, int hi) {
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
return hi - lo - 1;
}
public static void main(String[] args) {
String s = "a".repeat(8000);
long t0 = System.nanoTime();
int len = longest(s).length();
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("8000 letters: " + len + ", " + ms + " ms");
String t = "ab".repeat(4000) + "racecar" + "ba".repeat(4000);
System.out.println(t.length() + " letters: " + longest(t).length());
}
}
8000 letters: 8000, 22 ms
16007 letters: 16007
Problem 2: Palindrome Partitioning II (LeetCode 132)
Cut s into pieces so that every piece is a palindrome; return the fewest cuts. 1 ≤ n ≤ 2000.
| s | Answer | Cut |
|---|---|---|
aab |
1 | aa \| b |
banana |
1 | b \| anana |
racecarannakayak |
2 | racecar \| anna \| kayak |
a |
0 | already a palindrome |
ab |
1 | a \| b |
abcba |
0 | already a palindrome |
Obvious idea: every first piece
import java.util.*;
public class Main {
static int minCut(String s) {
return pieces(s, 0) - 1;
}
static int pieces(String s, int start) {
if (start == s.length()) return 0;
int best = Integer.MAX_VALUE;
for (int end = start; end < s.length(); end++)
if (isPal(s, start, end))
best = Math.min(best, 1 + pieces(s, end + 1));
return best;
}
static boolean isPal(String s, int i, int j) {
while (i < j)
if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
public static void main(String[] args) {
System.out.println(minCut("aab"));
System.out.println(minCut("banana"));
System.out.println(minCut("racecarannakayak"));
System.out.println(minCut("a"));
System.out.println(minCut("ab"));
System.out.println(minCut("abcba"));
}
}
1
1
2
0
1
0
Forty a's: every one of the 2^39 (over 500 billion) ways to cut is valid, and the recursion visits them all.
import java.util.*;
public class Main {
static int minCut(String s) {
return pieces(s, 0) - 1;
}
static int pieces(String s, int start) {
if (start == s.length()) return 0;
int best = Integer.MAX_VALUE;
for (int end = start; end < s.length(); end++)
if (isPal(s, start, end))
best = Math.min(best, 1 + pieces(s, end + 1));
return best;
}
static boolean isPal(String s, int i, int j) {
while (i < j)
if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
public static void main(String[] args) {
String s = "a".repeat(40);
long t0 = System.nanoTime();
int cuts = minCut(s);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("40 letters, cuts: " + cuts + ", " + ms + " ms");
}
}
Time Limit Exceeded (stopped after 25 s)
The DP recipe: two tables
| Table | Rule |
|---|---|
pal[i][j] |
s[i] == s[j] && (j - i < 2 \|\| pal[i + 1][j - 1]) |
| Fill order | pal[i + 1] is the row below: i from n - 1 down to 0 |
pieces[i] |
min over j < i with pal[j][i - 1] of pieces[j] + 1 |
| Base | pieces[0] = 0 |
| Answer | pieces[n] - 1 (cuts = pieces - 1) |
By hand: banana
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| prefix | (empty) | b | ba | ban | bana | banan | banana |
| pieces[i] | 0 | 1 | 2 | 3 | 2 (b + ana) | 3 (ba + nan) | 2 (b + anana) |
2 pieces = 1 cut.
import java.util.*;
public class Main {
static int minCut(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++)
pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
int[] pieces = new int[n + 1];
for (int i = 1; i <= n; i++) {
pieces[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++)
if (pal[j][i - 1]) pieces[i] = Math.min(pieces[i], pieces[j] + 1);
}
return pieces[n] - 1;
}
public static void main(String[] args) {
System.out.println(minCut("aab"));
System.out.println(minCut("banana"));
System.out.println(minCut("racecarannakayak"));
System.out.println(minCut("a"));
System.out.println(minCut("ab"));
System.out.println(minCut("abcba"));
}
}
1
1
2
0
1
0
The 40 a's, and 2,000 letters (the biggest LeetCode input):
import java.util.*;
public class Main {
static int minCut(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++)
pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
int[] pieces = new int[n + 1];
for (int i = 1; i <= n; i++) {
pieces[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++)
if (pal[j][i - 1]) pieces[i] = Math.min(pieces[i], pieces[j] + 1);
}
return pieces[n] - 1;
}
public static void main(String[] args) {
String s = "a".repeat(40);
long t0 = System.nanoTime();
int cuts = minCut(s);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("40 letters, cuts: " + cuts + ", " + ms + " ms");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 2000; i++) sb.append((char) ('a' + (i * i) % 3));
t0 = System.nanoTime();
cuts = minCut(sb.toString());
ms = (System.nanoTime() - t0) / 1000000;
System.out.println("2000 letters, cuts: " + cuts + ", " + ms + " ms");
}
}
40 letters, cuts: 0, 0 ms
2000 letters, cuts: 1, 17 ms
Every partition (LeetCode 131): backtracking
import java.util.*;
public class Main {
static void all(String s, int start, List<String> parts) {
if (start == s.length()) { System.out.println(parts); return; }
for (int end = start; end < s.length(); end++)
if (isPal(s, start, end)) {
parts.add(s.substring(start, end + 1));
all(s, end + 1, parts);
parts.remove(parts.size() - 1);
}
}
static boolean isPal(String s, int i, int j) {
while (i < j)
if (s.charAt(i++) != s.charAt(j--)) return false;
return true;
}
public static void main(String[] args) {
all("aab", 0, new ArrayList<>());
System.out.println("--");
all("noon", 0, new ArrayList<>());
}
}
[a, a, b]
[aa, b]
--
[n, o, o, n]
[n, oo, n]
[noon]
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// Longest palindromic substring: grow from each of the 2n - 1 centres.
int grow(const string& s, int lo, int hi) {
while (lo >= 0 && hi < (int)s.size() && s[lo] == s[hi]) { lo--; hi++; }
return hi - lo - 1;
}
string longest(const string& s) {
int start = 0, len = 0;
for (int c = 0; c < (int)s.size(); c++) {
int m = max(grow(s, c, c), grow(s, c, c + 1));
if (m > len) { len = m; start = c - (m - 1) / 2; }
}
return s.substr(start, len);
}
// Palindrome partitioning II: pal table (i from the bottom up) + pieces[i] over prefixes.
int minCut(const string& s) {
int n = s.size();
vector<vector<bool>> pal(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++)
pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
vector<int> pieces(n + 1, INT_MAX);
pieces[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (pal[j][i - 1]) pieces[i] = min(pieces[i], pieces[j] + 1);
return pieces[n] - 1;
}
int main() {
for (string s : {"babad", "cbbd", "bananas", "a", "ac", "malayalam"}) cout << longest(s) << "\n";
for (string s : {"aab", "banana", "racecarannakayak", "a", "ab", "abcba"}) cout << minCut(s) << "\n";
}
bab
bb
anana
a
a
malayalam
1
1
2
0
1
0
The same solutions in Python
# Longest palindromic substring: grow from each of the 2n - 1 centres.
def grow(s, lo, hi):
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo -= 1
hi += 1
return hi - lo - 1
def longest(s):
start, length = 0, 0
for c in range(len(s)):
m = max(grow(s, c, c), grow(s, c, c + 1))
if m > length:
length, start = m, c - (m - 1) // 2
return s[start:start + length]
# Palindrome partitioning II: pal table (i from the bottom up) + pieces[i] over prefixes.
def min_cut(s):
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
pieces = [0] + [float("inf")] * n
for i in range(1, n + 1):
for j in range(i):
if pal[j][i - 1]:
pieces[i] = min(pieces[i], pieces[j] + 1)
return pieces[n] - 1
for s in ["babad", "cbbd", "bananas", "a", "ac", "malayalam"]:
print(longest(s))
for s in ["aab", "banana", "racecarannakayak", "a", "ab", "abcba"]:
print(min_cut(s))
bab
bb
anana
a
a
malayalam
1
1
2
0
1
0
Three real bugs
Bug 1: only odd centres.
import java.util.*;
public class Main {
static String longest(String s) {
int start = 0, len = 0;
for (int c = 0; c < s.length(); c++) {
int m = grow(s, c, c);
if (m > len) { len = m; start = c - (m - 1) / 2; }
}
return s.substring(start, start + len);
}
static int grow(String s, int lo, int hi) {
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
return hi - lo - 1;
}
public static void main(String[] args) {
System.out.println(longest("cbbd"));
System.out.println(longest("abba"));
}
}
c
a
c instead of bb, a instead of abba: an even palindrome has no middle letter.
Bug 2: the pal table filled top down.
import java.util.*;
public class Main {
static int minCut(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
int[] pieces = new int[n + 1];
for (int i = 1; i <= n; i++) {
pieces[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++)
if (pal[j][i - 1]) pieces[i] = Math.min(pieces[i], pieces[j] + 1);
}
return pieces[n] - 1;
}
public static void main(String[] args) {
System.out.println(minCut("abcba"));
System.out.println(minCut("racecarannakayak"));
}
}
4
14
4 and 14 instead of 0 and 2: pal[0][4] reads pal[1][3] before it is filled, so long palindromes look like non-palindromes.
Bug 3: hi - lo + 1.
import java.util.*;
public class Main {
static String longest(String s) {
int start = 0, len = 0;
for (int c = 0; c < s.length(); c++) {
int odd = grow(s, c, c), even = grow(s, c, c + 1);
int m = Math.max(odd, even);
if (m > len) { len = m; start = c - (m - 1) / 2; }
}
return s.substring(start, start + len);
}
static int grow(String s, int lo, int hi) {
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
return hi - lo + 1;
}
public static void main(String[] args) {
System.out.println(longest("babad"));
}
}
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Range [-1, 4) out of bounds for length 5
at Main.longest(Main.java:11)
at Main.main(Main.java:21)
When grow stops, lo and hi are already outside the palindrome, so the length is 2 too big and the start lands at -1.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Every substring + check | O(n³) | O(1) | 8,000 letters: Time Limit Exceeded |
| Grow from 2n - 1 centres | O(n²) | O(1) | 8,000 letters: ~50 ms |
pal[i][j] table for LeetCode 5 |
O(n²) | O(n²) | works, more memory |
| Manacher | O(n) | O(n) | rarely needed |
| Min cut: every first piece | O(2^n) | O(n) | 40 letters: Time Limit Exceeded |
Min cut: pal + pieces |
O(n²) | O(n²) | 2,000 letters: ~30 ms |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
Only grow(s, c, c) |
c for cbbd, a for abba |
even palindromes have a gap centre | also grow(s, c, c + 1) |
pal table with i going up |
4 cuts for abcba |
pal[i + 1][j - 1] not filled yet |
i from n - 1 down |
return hi - lo + 1 |
StringIndexOutOfBoundsException: Range [-1, 4) out of bounds for length 5 |
lo, hi are one step outside |
hi - lo - 1 |
| Mixing substring and subsequence | wrong answers | subsequences may skip letters | LeetCode 516 is an interval DP |
Calling isPal inside the min-cut DP |
O(n³), slow at n = 2000 | rechecking every piece | precompute pal[i][j] |
Returning pieces[n] |
one too many | pieces vs cuts | pieces[n] - 1 |
Mini project: the train game app
Read a word; print its longest palindrome, the fewest cuts with the pieces (keep from[i] as in word break and walk back), and the number of palindromic substrings. Try racecarannakayak, malayalam and bananas.
Practice
1. Palindromic Substrings (LeetCode 647). Count every palindromic substring: grow from every centre and count each step.
2. Longest Palindromic Subsequence (LeetCode 516). Letters may be skipped: dp[i][j] = dp[i+1][j-1] + 2 if the ends match, else max(dp[i+1][j], dp[i][j-1]).
Solutions
import java.util.*;
public class Main {
// Palindromic Substrings (LeetCode 647): count every palindrome by growing from each centre.
static int countSubstrings(String s) {
int count = 0;
for (int c = 0; c < 2 * s.length() - 1; c++) {
int lo = c / 2, hi = lo + c % 2;
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) { count++; lo--; hi++; }
}
return count;
}
// Longest Palindromic Subsequence (LeetCode 516): letters need not be adjacent; interval DP.
static int longestPalSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++)
dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
}
return dp[0][n - 1];
}
public static void main(String[] args) {
System.out.println(countSubstrings("abc"));
System.out.println(countSubstrings("aaa"));
System.out.println(longestPalSubseq("bbbab"));
System.out.println(longestPalSubseq("cbbd"));
}
}
3
6
4
2
abc has 3 (each letter), aaa has 6 (a, a, a, aa, aa, aaa); bbbab → bbbb (4), cbbd → bb (2).
3. Print the pieces for racecarannakayak. Answer: racecar | anna | kayak.
Quick quiz
How many centres does "grow from the centre" try on level? A) 5 B) 9 C) 10 D) 25
Answer
B) 9. 5 letters + 4 gaps = 2 × 5 - 1. level itself grows from v.
Interview questions
- Why
2n - 1centres? Odd palindromes centre on a letter, even ones on a gap. - Why can you stop at the first mismatch? Any bigger palindrome with that centre would contain the mismatched pair.
- Complexity of expand-around-centre? O(n²) time, O(1) space.
- When would you use the
pal[i][j]table instead? When you need to ask "iss[i..j]a palindrome?" many times, as in partitioning. - Why fill
palfrom the bottom row up?pal[i][j]depends onpal[i + 1][j - 1], a row below. - How is min cut like word break? Both are DPs over prefixes; the "dictionary" is "any palindrome", and we take a minimum instead of OR.
- Is there an O(n) solution? Manacher's algorithm, for the longest palindromic substring.
Glossary
| Term | Meaning |
|---|---|
| Palindrome | Reads the same forwards and backwards |
| Substring | Consecutive letters |
| Subsequence | Letters in order, gaps allowed |
| Centre | A letter (odd) or a gap (even) |
| Expand around centre | Step outwards while the letters match |
| Partition | Cutting into consecutive pieces |
pal[i][j] |
Is s[i..j] a palindrome? |
pieces[i] |
Fewest palindromes for the first i letters |
| Backtracking | Choose, recurse, undo |
| Manacher's algorithm | O(n) longest palindromic substring |
Summary
- A palindrome is a smaller palindrome plus the same letter on each side, so grow from each of the
2n - 1centres: O(n²), O(1) space, lengthhi - lo - 1. - Min cut:
pal[i][j]filled from the bottom up, thenpieces[i] = min pieces[j] + 1, answerpieces[n] - 1. - Every partition: backtracking with the palindrome check.
- Next episode: regular expression matching, a hard DP on two strings with dot and star.