Coding interview problems › Backtracking

🧩 Backtracking Medium

Palindrome Partitioning

Palindrome Partitioning explained: backtrack over cut positions, keep only palindromic pieces and list every partition, with tested Python and pitfalls.

Also searched as: palindrome partitioning backtracking · split a string into palindromes · all palindromic partitions of a string

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

Turn pruning on in the Backtracking lab and watch whole subtrees disappear; here every non-palindromic prefix prunes its subtree the same way.

Also useful: 2D DP Table: LCS & Edit Distance

Open the playground →

The problem

Given a string, return every way to cut it into pieces such that every piece is a palindrome.

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

The key insight

Choose where the first piece ends. If that prefix is a palindrome, keep it and partition the rest of the string the same way; if not, that branch is pruned immediately. A precomputed table of which substrings are palindromes makes each check O(1).

Brute force first: Trying all 2n-1 ways to place cuts and then checking every piece repeats the same palindrome checks many times.

Step-by-step approach

  1. Optionally precompute is_pal[i][j] for all substrings: true if s[i] == s[j] and the inside is a palindrome.
  2. Define dfs(start): if start == len(s), record a copy of path.
  3. For each end e from start to the last index, if s[start..e] is a palindrome: append it, call dfs(e + 1), pop.
  4. Call dfs(0).

Python solution

PYTHON 3tested
def partition(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
    out, path = [], []

    def dfs(start):
        if start == n:
            out.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:         # prune non-palindromic pieces
                path.append(s[start:end + 1])
                dfs(end + 1)
                path.pop()

    dfs(0)
    return out

Complexity

TimeO(n · 2^n)
SpaceO(n²)

A string of identical letters has 2n-1 partitions, each copied in O(n). The palindrome table is O(n²) space.

Common mistakes

Frequently asked questions

What is the time and space complexity of Palindrome Partitioning?

O(n × 2^n) time in the worst case (all equal letters), plus O(n²) to build the palindrome table, which is also the main extra space.

How do I find the minimum number of cuts instead?

That is Palindrome Partitioning II, a DP: cuts[i] = min(cuts[j - 1] + 1) over every j where s[j..i] is a palindrome. It runs in O(n²).

Do I need the palindrome table?

No, checking each piece directly is still correct. The table removes repeated work and is a nice way to show interviewers you see the overlapping subproblems.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.