Palindrome Partitioning

1. Problem & Core Objective

Given a string s, partition it so that every substring in the partition is a palindrome. Return all possible partitionings.

s = "aab"
→ [["a","a","b"], ["aa","b"]]

s = "a"
→ [["a"]]

Constraints: 1 <= s.length <= 16 · lowercase letters only

What's actually being tested: that the "choices" at each step are where to cut, not which element to take — and that an invalid choice is pruned by a validity check before recursing. It's the first question here where the candidate set is computed rather than given.

2. First-Principles Thought Process

What is being chosen

Previous questions chose elements. Here the choice is how long the next piece is.

At position start, the candidates are the substrings s[start..end] for every end from start to the end of the string. Choosing one commits to that piece and moves the search to end + 1.

"aab", start = 0:
    take "a"   → recurse at 1
    take "aa"  → recurse at 2
    take "aab" → recurse at 3

That's the same loop shape as before — for (int end = start; end < n; end++) — with the loop variable naming a cut point rather than an index into a list.

The constraint prunes the branch

Not every cut is legal: the piece must be a palindrome. So:

if (!isPalindrome(s, start, end)) continue;   // this cut is invalid — try a longer piece

Note it's continue, not break. A non-palindromic piece doesn't mean longer pieces are also invalid — "ab" isn't a palindrome but "aba" might be. That's the opposite of Combination Sum's sorted break, and the distinction matters: break is only valid when failure is monotonic in the loop variable.

The base case

When start == s.length(), the whole string has been consumed by valid pieces, so the current path is a complete partitioning — record it.

Unlike Subsets, a partial path is not an answer; it's a prefix of one.

Counting the work

There are 2^(n−1) ways to cut a string of length n — a cut either happens or doesn't at each of the n − 1 gaps. So the upper bound is O(n · 2^n), and the palindrome check prunes from there.

At n = 16 that's 32,768 partitionings in the worst case — which needs a string like "aaaaaaaaaaaaaaaa", where every piece is a palindrome and nothing is ever pruned.

3. Solution Paths

Approach 1 — Generate all partitions, filter at the end (brute force)

public List<List<String>> partition(String s) {
    List<List<String>> all = new ArrayList<>();
    buildAll(s, 0, new ArrayList<>(), all);

    List<List<String>> result = new ArrayList<>();
    for (List<String> p : all) {                       // filter AFTER generating
        boolean ok = true;
        for (String piece : p) if (!isPalindrome(piece)) { ok = false; break; }
        if (ok) result.add(p);
    }
    return result;
}

private void buildAll(String s, int start, List<String> path, List<List<String>> all) {
    if (start == s.length()) { all.add(new ArrayList<>(path)); return; }
    for (int end = start; end < s.length(); end++) {
        path.add(s.substring(start, end + 1));
        buildAll(s, end + 1, path, all);
        path.remove(path.size() - 1);
    }
}

• Time O(n · 2^n) to generate, plus O(n · 2^n) to filter · Space O(n · 2^n)

Counter-questions on this approach

⭐ "It generates all 2^(n−1) partitions and filters. What does pruning save?"

Everything below an invalid cut. If s[0..1] isn't a palindrome, then no partition beginning with that piece can be valid — but this version still explores every way to cut the remaining suffix beneath it.

Checking before recursing abandons that whole subtree. On a string with few palindromic substrings, that's the difference between 2^15 partitions and a handful.

⭐ "How much does it actually matter at n = 16?"

2^15 = 32,768 partitions, each up to 16 pieces — so roughly 5 × 10^5 operations to generate and the same to filter. It would pass.

So this is a correctness-of-approach objection rather than a timeout. But the pruned version is the same length, and it's the habit the section is teaching: test the constraint where it can first fail.

"Filtering also holds every partition in memory first."

Right — O(n · 2^n) live objects, versus O(n) for the pruned version plus the valid results. On a string of all identical characters both are the same, but on a typical string the pruned version's footprint is tiny.

Approach 2 — Backtracking with the palindrome check as a prune (optimal)

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(String s, int start, List<String> path,
                       List<List<String>> result) {
    if (start == s.length()) {                      // consumed the whole string
        result.add(new ArrayList<>(path));
        return;
    }

    for (int end = start; end < s.length(); end++) {
        if (!isPalindrome(s, start, end)) continue;  // PRUNE: this cut is illegal

        path.add(s.substring(start, end + 1));       // choose
        backtrack(s, end + 1, path, result);         // explore from after the piece
        path.remove(path.size() - 1);                // un-choose
    }
}

private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi)
        if (s.charAt(lo++) != s.charAt(hi--)) return false;
    return true;
}

Trace — s = "aab":

Result [["a","a","b"], ["aa","b"]] ✓

• Time O(n · 2^n) worst case · Space O(n) depth

Counter-questions on this approach

⭐ "Why continue and not break?"

Because failure isn't monotonic in end. "ab" isn't a palindrome, but "aba" is — a longer piece starting at the same place can succeed where a shorter one failed.

break is only valid when a failure guarantees every later candidate also fails, which was true in Combination Sum because the array was sorted and values only grew. Here there's no such ordering, so I must test every cut point.

Reaching for break out of habit would silently drop valid partitions.

⭐ "The palindrome check is O(n) and runs at every node. Can that be improved?"

Yes — precompute a table. isPal[i][j] is true when s[i..j] is a palindrome, built by expanding around centres or by DP in O(n²) time and space:

Java

for (int len = 1; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        isPal[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || isPal[i+1][j-1]);
    }

Then the check is O(1), dropping the total to O(2^n). At n = 16 the table is 256 booleans — trivially cheap, and the right answer if asked to optimise.

⭐ "Why pass end + 1 to the recursive call?"

Because the piece s[start..end] has been consumed, so the next piece starts immediately after it. Passing end would re-include the last character in the following piece, producing overlapping pieces rather than a partition.

It's the partition analogue of i + 1 in Subsets: move past what you took.

"Why record only at start == s.length() rather than at every node?"

Because a partial path doesn't cover the whole string. ["a"] is not a partitioning of "aab".

Same principle as before: record where the problem's definition of complete is met. Subsets records everywhere, Combination Sum when the remainder hits zero, this when the string is exhausted.

"s.substring(start, end + 1) allocates. Is that a problem?"

It's O(piece length) per call, and Java strings are immutable so each substring is a fresh object. With at most 2^n partitions of n pieces, that's a real constant factor.

You could store (start, end) index pairs and materialise the strings only for recorded results. Worth mentioning; at n = 16 it isn't necessary.

"Is the worst case reachable?"

Yes — "aaaaaaaaaaaaaaaa", where every substring is a palindrome so nothing is ever pruned. That gives all 2^15 partitions, which is the intended upper bound and why n is capped at 16.

Comparison

4. Why the Optimal Wins

Checking the palindrome before recursing abandons the entire subtree below an illegal cut. Filtering afterwards explores that subtree in full and then discards every result it produced.

And the precomputed table is worth knowing as the natural next step: the palindrome test is asked repeatedly about overlapping ranges, which is exactly the signal for memoising it.

The framing worth keeping:

When the choice is "where to cut", the loop variable is the cut point and the validity check is the prune. Use continue, not break — break is only correct when failure is monotonic in the loop variable.

5. Java Prerequisites

Partition backtracking

if (start == s.length()) { result.add(new ArrayList<>(path)); return; }
for (int end = start; end < s.length(); end++) {
    if (!isValid(s, start, end)) continue;
    path.add(s.substring(start, end + 1));
    backtrack(s, end + 1, path, result);
    path.remove(path.size() - 1);
}

In-place palindrome check — no substring allocation:

private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;
    return true;
}

substring(start, end + 1) — the second argument is exclusive, so + 1 is needed to include end.

continue vs break — break requires that a failure at i implies failure at every j > i. Verify that before using it.

6. Interview Communication Guide

Clarifying questions: Must every piece be a palindrome (yes)? Are single characters palindromes (yes — so a partitioning always exists)? Does the order of partitions matter (no)? What's the maximum length (16 — so 2^15 partitions worst case)?

The pitch

"The choices here aren't elements — they're cut points. At position start, the candidates are the substrings s[start..end] for every end, and choosing one moves the search to end + 1.

So it's the same loop, with the loop variable naming a cut rather than indexing a list.

The constraint prunes the branch: if s[start..end] isn't a palindrome, that cut is illegal, so I skip it without recursing. That abandons the whole subtree beneath it — every way of cutting the remaining suffix.

The detail I'd emphasise is continue, not break. Failure isn't monotonic in end: "ab" isn't a palindrome but "aba" is, so a longer piece starting at the same place can succeed where a shorter one failed. break is only valid when a failure guarantees all later candidates fail too — which was true in Combination Sum because the array was sorted, and is false here.

I record only when start reaches the end of the string, because a partial path doesn't cover the whole input.

O(n · 2^n) worst case — there are 2^(n−1) ways to cut a string, and the worst input is all identical characters where nothing is ever pruned.

If asked to optimise, I'd precompute a palindrome table: isPal[i][j] in O(n²) time and space, which makes the check O(1) and drops the total to O(2^n). At n = 16 that's a 256-entry table — cheap."

Edge cases to volunteer:

Name "ab" and "aaaa". They bracket the pruning: one where almost everything is cut, one where nothing is. And "aba" is the case that proves break would be wrong — a two-character piece fails where the three-character piece succeeds.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the MINIMUM number of cuts instead of all partitions."

LeetCode 132, and a genuinely different problem — it's DP, not backtracking. cuts[i] = minimum cuts for the prefix ending at i, computed with the same palindrome table in O(n²). Enumerating all partitions to find the smallest would be exponential for a polynomial answer, which is worth saying explicitly.

⭐ "Precompute the palindrome table."

isPal[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPal[i+1][j-1]), filled by increasing length so the inner value is ready. O(n²) time and space, and it makes the check O(1). This is the expected optimisation if asked to go faster.

"Partition so every piece has length exactly k."

No longer a search — there's one partitioning if k divides n, none otherwise. A good reminder that the branching came from the variable piece length.

"Count the partitionings without listing them."

DP over prefixes: ways[i] = sum of ways[j] for every j where s[j..i-1] is a palindrome. O(n²) with the table, versus exponential enumeration. Same counting-versus-listing gap as in Combination Sum.

"What if n were 1000?"

Enumeration is impossible — 2^999 partitions. Only the DP variants (minimum cuts, count) remain feasible at O(n²) = 10^6. This is where the problem stops being a backtracking question.

"Partition into pieces that are all anagrams of each other."

The validity check changes from isPalindrome to a character-count comparison against the first piece. The skeleton is untouched — which is the point of having a skeleton. Note the check is no longer local to the piece, since it depends on an earlier choice, so it would take the path as a parameter.