#131 Palindrome Partitioning

Mediumsolve on LeetCode ↗

frequently reported atBloomberg Amazon Meta Google

the problem

In plain words

Split s into pieces so that every piece is a palindrome. Return every such partition.

in s = "aab"

out [["a","a","b"],["aa","b"]]

in s = "a"

out [["a"]]

1 ≤ s.length ≤ 16
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking: combinations & partitions Interval DP

The choice at each step is where the next piece ends. Only palindromic pieces are allowed, which prunes the 2ⁿ⁻¹ ways to cut the string.

solutions

From brute force to optimal

From start, try every end; if s[start..end] is a palindrome (two-pointer check), take it and recurse from end + 1.

start == n → record path.
For end in start..n−1: if palindrome, add piece, recurse(end + 1), remove.

timeO(n·2ⁿ)

Up to 2ⁿ⁻¹ partitions (all-same letters), with O(n) checking and copying per step.

spaceO(n)

Recursion depth and path (excluding output).

javajava.util.*

1class Solution {2    public List<List<String>> partition(String s) {3        List<List<String>> result = new ArrayList<>();4        backtrack(s, 0, new ArrayList<>(), result);5        return result;6    }7 8    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {9        if (start == s.length()) {10            result.add(new ArrayList<>(path));11            return;12        }13        for (int end = start; end < s.length(); end++) {   // next piece is s[start..end]14            if (!isPalindrome(s, start, end)) continue;    // not a palindrome → prune15            path.add(s.substring(start, end + 1));16            backtrack(s, end + 1, path, result);17            path.remove(path.size() - 1);18        }19    }20 21    private boolean isPalindrome(String s, int lo, int hi) {22        while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;23        return true;24    }25}

pal[i][j] = s[i] == s[j] && (j − i < 2 || pal[i+1][j−1]); backtracking then checks a piece in O(1).

Fill pal bottom-up (i from n−1 down).
Same backtracking, using pal[start][end].

timeO(n·2ⁿ)

Same worst-case output size, but no repeated palindrome checks: O(n²) table + O(1) lookups.

spaceO(n²)

The table; recursion adds O(n).

javajava.util.*

1class Solution {2    public List<List<String>> partition(String s) {3        int n = s.length();4        boolean[][] pal = new boolean[n][n];          // pal[i][j] = s[i..j] is a palindrome5        for (int i = n - 1; i >= 0; i--) {6            for (int j = i; j < n; j++) {7                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);8            }9        }10        List<List<String>> result = new ArrayList<>();11        backtrack(s, 0, pal, new ArrayList<>(), result);12        return result;13    }14 15    private void backtrack(String s, int start, boolean[][] pal, List<String> path, List<List<String>> result) {16        if (start == s.length()) {17            result.add(new ArrayList<>(path));18            return;19        }20        for (int end = start; end < s.length(); end++) {21            if (!pal[start][end]) continue;              // O(1) lookup instead of O(n) check22            path.add(s.substring(start, end + 1));23            backtrack(s, end + 1, pal, path, result);24            path.remove(path.size() - 1);25        }26    }27}

in the room

How to say it in the interview

talk track

Describe it as "choose the next cut"; mention the table as a precompute to avoid re-checking the same substring.

traps

Saving path itself instead of new ArrayList<>(path) — every saved partition then changes as you backtrack.
Filling the table with i going up: pal[i + 1][j − 1] is not ready yet. Go from i = n − 1 down.
Forgetting to remove the last piece after the recursive call returns.

what they ask next

Follow-ups

Minimum number of cuts (LC 132)?

That's DP, not backtracking: cuts[j] = min over palindromic s[i..j] of cuts[i−1] + 1 — O(n²).

before you submit

Edge cases to test

One letter → [["a"]].
All the same letter: "aaaa" → 2³ = 8 partitions, the worst case.
No palindrome longer than 1 ("abc") → exactly one partition.

practise next