SyntaxPilot
Courses/DSA and Coding Problems/Lesson 72
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 72 of 90

Palindromes: longest palindromic substring and palindrome partitioning

queued

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; k pieces need k - 1 cuts.
  • pal[i][j]: a table saying whether s[i..j] is a palindrome.
  • pieces[i]: the fewest palindromes that the first i letters 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² / 2 substrings × up to n / 2 comparisons = O(n³).
  • Checking anana compares the outer as, then the ns, then the middle; checking nan compares the same ns 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

  1. Why 2n - 1 centres? Odd palindromes centre on a letter, even ones on a gap.
  2. Why can you stop at the first mismatch? Any bigger palindrome with that centre would contain the mismatched pair.
  3. Complexity of expand-around-centre? O(n²) time, O(1) space.
  4. When would you use the pal[i][j] table instead? When you need to ask "is s[i..j] a palindrome?" many times, as in partitioning.
  5. Why fill pal from the bottom row up? pal[i][j] depends on pal[i + 1][j - 1], a row below.
  6. 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.
  7. 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 - 1 centres: O(n²), O(1) space, length hi - lo - 1.
  • Min cut: pal[i][j] filled from the bottom up, then pieces[i] = min pieces[j] + 1, answer pieces[n] - 1.
  • Every partition: backtracking with the palindrome check.
  • Next episode: regular expression matching, a hard DP on two strings with dot and star.