Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Palindrome Partitioning in Java: Choose a Valid Prefix, Partition the Rest

Enumerate palindrome partitions by choosing valid prefixes, copying completed paths and undoing; understand substring costs and minimum-cut differences.

MediumRecursion and backtrackingPattern: recursion, backtracking, two pointers

Problem statement

Split a string into contiguous, nonempty pieces so that each piece reads the same forward and backward. Return all complete partitions. Every original character must appear once, in its original order.

LeetCode Palindrome Partitioning permits 1–16 lowercase letters. For aab, both [a,a,b] and [aa,b] qualify. This does not ask for minimum cuts, and it does not let us rearrange characters as Palindrome Permutation II does.

Constraints & requirements

CONTRACT
LeetCode: 1–16 lowercase letters. This is enumeration, not minimum cuts or palindrome permutation. Try every prefix length and continue only for a palindromic prefix.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    s="aab"
    Output
    [["a","a","b"],["aa","b"]]

    a, aa and b are palindromes; ab and aab are not.

  2. Example 2 Case 2

    Input
    s="a"
    Output
    [["a"]]

    A one-letter piece reads the same both ways.

  3. Example 3 Case 3

    Input
    s="aba"
    Output
    [["a","b","a"],["aba"]]

    The complete string and its one-letter pieces give different partitions.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Choose the first piece only from a prefix of the remaining string.

02Hint 2

Reject a prefix if its two ends fail the palindrome check.

03Hint 3

An empty remaining suffix is a complete answer; save a list copy, then undo the last piece.

How to think before coding

This is a CUT problem, not a rearrangement problem. A call owns the remaining suffix and a list of already chosen pieces. Try every nonempty prefix length; recurse only after that prefix passes the palindrome check. An empty suffix completes a partition. Copy the list at success and remove the last piece after each child, keeping the earlier pieces intact.

Brute force and the improvement

A length-n string has n−1 internal cut positions. Try every one of the 2^(n−1) cut masks, then check whether every resulting piece is palindromic. Checking a whole partition costs O(n), so the baseline takes O(n·2^n) time with O(n) working state, excluding returned partitions. Instead, reject a nonpalindromic prefix before making more cuts after it. The improved backtracker still has exponential output when every substring is valid; pruning does not eliminate that unavoidable case.

Intuition: decide the next cut

Choose the first piece from a prefix of the remaining string. For aab, try a, aa and aab. The first two are palindromes; the last is not.

After choosing a, the remaining input is ab. Its prefix a is legal, but ab is not. Choosing the legal a leaves b, which completes the partition. After that branch finishes, return and try aa at the original level.

The state has two meanings: remaining is the suffix still to cover, while path records the already chosen pieces. We save an answer only when remaining is empty—not whenever we see a palindrome.

Algorithm

  1. If no input remains, copy path into the result.
  2. Try each nonempty prefix of the current suffix.
  3. Check it with two pointers moving inward.
  4. If it is a palindrome, append it and recursively partition the rest.
  5. Remove that appended piece after the child returns.

A failed prefix creates no recursive child. This is pruning by a local property, not removing characters from the string arbitrarily.

Java solution

new ArrayList<>(path) copies the list, not the strings inside it. This is sufficient because strings are immutable; later removal from the working path cannot change the saved list.

Java
import java.util.*;

class Solution {
    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        partitionSuffix(s, new ArrayList<>(), result); // No characters consumed yet.
        return result;
    }
    private static void partitionSuffix(String remaining, List<String> path, List<List<String>> result) {
        if (remaining.isEmpty()) { // Every original character belongs to exactly one chosen piece.
            result.add(new ArrayList<>(path)); // Copy the list; its String elements are immutable.
            return;
        }
        for (int end = 1; end <= remaining.length(); end++) { // Prefix end is exclusive; no empty pieces.
            String piece = remaining.substring(0, end);
            if (!palindromePiece(piece)) continue; // Reject an invalid cut before exploring its suffix.
            path.add(piece); // Choose this valid prefix.
            partitionSuffix(remaining.substring(end), path, result); // Cover the ENTIRE remaining suffix.
            path.remove(path.size() - 1); // Restore the parent's partition, not a saved answer.
        }
    }
    private static boolean palindromePiece(String piece) {
        int left = 0, right = piece.length() - 1;
        while (left < right) {
            if (piece.charAt(left) != piece.charAt(right)) return false; // One mismatched pair is enough.
            left++; right--; // Compare the smaller interior.
        }
        return true; // Empty interior or one center cannot break symmetry.
    }

    public static void main(String[] args) {
        System.out.println(partition("aab")); // [[a, a, b], [aa, b]]
    }
}

The invocation prints [[a, a, b], [aa, b]]; Java’s list display does not quote strings. Those are partitions of one unchanged string, not two rearrangements.

Recursion tree and dry run

Numbered illustrated dry run for Palindrome Partitioning; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: s = "aab"

What to track: remaining is the unconsumed suffix; path is shared. end is an exclusive prefix boundary. Every accepted piece must pass palindromePiece before recursion.

  1. Take the first one-letter prefix

    Java operationpath.add(piece);
    Statepiece = "a"; path = ["a"]; child remaining = "ab"

    A one-letter string is a palindrome. The child covers the entire remaining suffix, not a rearranged string.

  2. Finish the one-letter route

    Java operationpartitionSuffix(remaining.substring(end), path, result);
    Statechoose "a", then "b"; path = ["a","a","b"]; remaining = ""

    Every original character has been consumed exactly once.

  3. Save and restore the pieces

    Java operationresult.add(new ArrayList<>(path));
    Statesave ["a","a","b"]; returning callers remove "b" and the second "a"; path = ["a"]

    The independent saved list remains unchanged while the shared path is shortened.

  4. Reject a larger nonpalindromic prefix

    Java operationif (!palindromePiece(piece)) continue;
    Stateat remaining = "ab", piece = "ab" fails; no child is created

    After exhausting this suffix frame, the root removes its first "a", restoring path = [].

  5. Try the root’s two-letter prefix

    Java operationpath.add(piece);
    Stateroot piece = "aa" passes; child remaining = "b"; path becomes ["aa","b"]

    This is a different set of cut positions. Its empty-suffix child saves the second partition.

  6. Finish the remaining root choice

    Java operationif (!palindromePiece(piece)) continue;
    Staterestored path = []; root piece = "aab" fails; two snapshots remain

    Checking all root prefix lengths completes the enumeration without inventing noncontiguous pieces.

Final result: [["a","a","b"],["aa","b"]]

Worked example · read from top to bottom
remaining aab, path []
├─ choose a → remaining ab, path [a]
│  ├─ choose a → remaining b, path [a,a]
│  │  └─ choose b → empty suffix → save [a,a,b]
│  └─ prefix ab is not a palindrome → skip
├─ choose aa → remaining b, path [aa]
│  └─ choose b → empty suffix → save [aa,b]
└─ prefix aab is not a palindrome → skip

After the first save, undo b, then a. The root path becomes empty before choosing aa. The result’s saved list still contains a,a,b because it is a separate object.

For aba, the root also tries ab, but its mismatched ends reject that branch. The complete prefix aba is legal and produces a one-piece partition. A partition need not contain more than one piece.

Why it works

At every call, concatenating path and remaining reconstructs the original string. Choosing a prefix and passing the leftover suffix preserves coverage and order. Each chosen piece has passed a palindrome check, so reaching an empty suffix proves a valid complete partition.

Every valid partition has a first palindromic prefix and a valid partition of its remaining suffix. Trying every prefix and applying the same reasoning recursively therefore reaches every valid cut sequence once.

Complexity and alternative approaches

There are n−1 potential boundaries, so there can be 2^(n−1) complete partitions; repeated identical letters reach that maximum. Output alone can require O(n·2^n) references/characters.

For this substring-based version, a conservative time bound is O(n²·2^n) when prefix scans, palindrome checks, copied substrings and saved lists are included. It is an upper bound, not a claim that every input performs that much work.

The stack and path have O(n) entries, but Java 17 substring copies create separate string data. Simultaneously live suffixes can have lengths n,n−1,…,1, giving O(n²) auxiliary character storage, excluding output. Calling all auxiliary storage O(n) would ignore those suffix copies.

An index-based backtracker can keep the original string instead of copying remaining suffixes. A precomputed palindrome table adds O(n²) storage/preprocessing and answers each substring check in constant time; traversal still must produce every returned partition. Minimum-cut DP returns a number rather than these lists, so it is a different task.

Common mistakes

  • Saving a partial path before consuming all characters.
  • Allowing empty pieces, which can also prevent recursion from shrinking.
  • Saving path itself so later undo changes old answers.
  • Reordering characters instead of choosing cut positions.
  • Calling a list copy a deep copy, or ignoring live substring allocations.

Practice next

Next lessonPalindrome Permutation II

Back to Recursion and backtracking →