Palindrome Partitioning

Table of Contents +

Palindrome Partitioning looks scary at first. You see a string and you have to break it into pieces. But every piece must read the same forwards and backwards. This question is really a test of one skill. Can you try a choice, go deeper, and then undo it cleanly? That undo step is the heart of backtracking.

🎯 The Problem

You get a string. You cut it into pieces where every piece is a palindrome.

The rules:

  • A palindrome reads the same both ways, like aba or cc.
  • Every piece in a cut must be a palindrome.
  • A single letter is always a palindrome.
  • Return every possible way to cut the string like this.
Input:  s = "aab"
Output: [["a","a","b"], ["aa","b"]]


Explanation: Each listed piece is a palindrome.
"a", "aa", and "b" all read the same forwards and backwards.

Here is the string split shown as a picture. We pick a cut point, check the left piece, then deal with the rest.

s = aab

cut: a | ab

cut: aa | b

cut: aab

a is palindrome -> keep, recurse on ab

aa is palindrome -> keep, recurse on b

aab is NOT palindrome -> stop

🐢 Approach 1: All Cut Sets Then Filter (Brute Force)

The idea:

  • A cut can go in any gap between two letters.
  • List every set of cut positions, so every way to split the string.
  • For each split, check that every piece is a palindrome.
  • Keep the splits where all pieces pass.

Why it is weak:

  • It builds splits with bad pieces and only rejects them at the end.
  • It does the palindrome check on whole splits, late.
  • Work is wasted on branches that were dead from the first piece.

Here is the all-cut-sets code for that idea:

palindrome_partitioning_brute_force.py
def partition(s):
    result = []


    def dfs(index, path):
        if index == len(s):
            if all(piece == piece[::-1] for piece in path):
                result.append(path[:])
            return
        for end in range(index + 1, len(s) + 1):
            dfs(end, path + [s[index:end]])


    dfs(0, [])
    return result

⚡ Approach 2: Backtracking With Prefix Check (Best)

The idea in one line: cut from the front, keep only palindrome prefixes, and recurse on the rest.

How it works:

  • Always cut from the front of the remaining string.
  • Try the first letter, then the first two, then the first three. Each is a prefix.
  • For each prefix, ask: is it a palindrome?
  • If yes, keep it as a piece and recurse on the rest.
  • If no, skip it and try a longer prefix.

When a path finishes:

  • The remaining string becomes empty.
  • Every letter is used. The collected pieces form one valid answer.
  • Save a copy of it.

Why it is fast:

  • A bad prefix kills its branch right away. No wasted deeper work.
  • The add, recurse, remove pattern explores every path without mixing them up.

Steps to Solve

  1. Start at the front of the string with an empty list of pieces.
  2. Try every prefix length, from one letter up to the whole remaining string.
  3. For each prefix, check if it is a palindrome.
  4. If it is a palindrome, add it to the current list of pieces.
  5. Recurse on the part of the string after that prefix.
  6. After the recursion returns, remove that last piece so you can try a longer prefix.
  7. When the remaining string is empty, save a copy of the current list as one answer.

Here is the decision tree for aab. Each branch is one cut we try. A dead end means the prefix was not a palindrome.

start: aab

take a -> rest ab

take aa -> rest b

take aab -> NOT palindrome, stop

take a -> rest b

take ab -> NOT palindrome, stop

take b -> rest empty -> save a,a,b

take b -> rest empty -> save aa,b

This Python version uses a list as the running path and appends a copy whenever the string is fully used.

palindrome_partitioning.py
def is_palindrome(s):
    return s == s[::-1]              # same forwards and backwards




def partition(s):
    result = []


    def backtrack(start, path):
        if start == len(s):         # whole string is used up
            result.append(path[:])  # save a copy of this answer
            return
        for end in range(start + 1, len(s) + 1):  # every prefix length
            prefix = s[start:end]
            if is_palindrome(prefix):             # keep only palindromes
                path.append(prefix)               # add the piece
                backtrack(end, path)              # recurse on the rest
                path.pop()                        # remove it (backtrack)


    backtrack(0, [])
    return result




for part in partition("aab"):
    print("[" + ",".join('"' + p + '"' for p in part) + "]")

The output of the above code will be:

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

Let us read the Python version line by line. This is where the backtracking pattern becomes clear.

def is_palindrome(s): is a small helper. It returns True when the string equals its own reverse. The slice s[::-1] is Python’s quick way to reverse a string. So this one line answers our key question for each prefix.

if start == len(s): is the stop condition. start is the position we have reached in the string. When start reaches the length, every letter has been placed into some piece. So the current path is a complete valid answer.

result.append(path[:]) saves it. The [:] makes a copy. This matters a lot. If we saved path directly, later changes would corrupt the saved answer. So we freeze a snapshot here.

for end in range(start + 1, len(s) + 1): tries every prefix length. end is where the prefix stops. We start the prefix at start and stretch it out one letter at a time.

prefix = s[start:end] cuts out that chunk. Then if is_palindrome(prefix): keeps only the good cuts. A cut that is not a palindrome is ignored, so that branch dies.

path.append(prefix) makes the choice. backtrack(end, path) goes deeper on the leftover part starting at end. Then path.pop() undoes the choice. This undo is the backtrack. It lets the loop try a longer prefix on a clean slate.

⏱️ Time and Space Complexity

In the worst case every prefix is a palindrome, like the string aaaa. Then at each position we can choose to cut or not cut. That gives about 2 choices per gap, so the number of partitions grows like 2 to the power of n. For each partition we also copy a list of pieces, which costs O(n). So the time is O(n × 2ⁿ). The recursion depth and the path use O(n) space, not counting the output itself.

Approach Time Complexity Space Complexity
All cut sets then filter (brute force) O(n × 2ⁿ), checks late O(n)
Backtracking with palindrome check O(n × 2ⁿ) O(n)

Tip

The add, recurse, remove pattern shows up in almost every backtracking problem. Once you spot it here, you will spot it everywhere. So practice saying it out loud while you code.

🧩 Key Takeaways

  • ✅ Always cut from the front, trying every prefix length one at a time.
  • ✅ Keep a prefix only when it is a palindrome, then recurse on what is left.
  • ✅ When the remaining string is empty, you have one full valid answer.
  • ✅ Always save a copy of the path, never the path itself, or later changes will ruin it.
  • ✅ The add, recurse, remove pattern is the core of all backtracking.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What must every piece of the partition be?

    Why: Every piece must read the same forwards and backwards, which means it must be a palindrome.

  2. 2

    When do we save the current path as a valid answer?

    Why: When start reaches the end of the string, every letter is used and the path is one complete answer.

  3. 3

    Why do we save a copy of the path instead of the path itself?

    Why: The path keeps changing as we add and remove pieces, so we freeze a copy to protect the saved answer.

  4. 4

    What is the purpose of the pop or remove step after recursion?

    Why: Removing the last piece restores the previous state, which is the backtracking step that lets us explore other cuts.

Score: 0 / 4

🚀 What’s Next?

Previous Permutations Next Letter Combinations of a Phone Number