What is the brute force approach and complexity for Palindrome Partitioning?

Try all 2^(n−1) cut sets and keep one only if every piece is a palindrome with time complexity O(N · 2^(N−1)) and space complexity O(N).

What is the optimal approach and complexity for Palindrome Partitioning?

Fill a palindrome table in O(N²); the search then checks each piece in O(1) with optimal time complexity O(N² + N · 2^N) and space complexity O(N²).

How do you identify the pattern for Palindrome Partitioning?

Look for key signals in the prompt: "every piece is a palindrome" indicates The rule is checked on each piece, so a bad piece can stop its branch right away.; "find every way to cut" indicates The answer is a list of all valid cut sets, so every valid route must be kept, not just one count.; "string" indicates The choices are cut points. After a cut, the rest of the string is the same problem, only shorter..

Palindrome Partitioning

Medium·LeetCode #131Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBacktracking → String partitioning (cut and recurse on the rest)

Complexity:O(N · 2^(N−1))→O(N² + N · 2^N)

Key Insight

Fill isPal[i][j] once for every substring, using isPal[i][j] = (s[i] == s[j]) and isPal[i+1][j−1]. Then run the same backtracking as the better approach, but each piece check is a table lookup.

Core Validity Invariant

Every piece must be a palindrome, so the search cuts s[start..end] only when isPal[start][end] is true. The table answers that in O(1), so no letter is compared again during the search.

Problem

You are given a string s. Cut s into pieces so that every piece is a palindrome. A palindrome reads the same forwards and backwards, such as aa or aba. Find every way to cut s like this. Each way is a list of pieces that, joined in order, give back s.

Input

A string s of lowercase letters.

Output

A list of every valid way to cut s. Each way is a list of pieces.

Example 1

Input: s = "aab"

Output: [[a, a, b], [aa, b]]

a, a and b are palindromes, and so are aa and b. The pieces ab and aab are not palindromes, so they cannot be used.

Example 2

Input: s = "a"

Output: [[a]]

A single letter is a palindrome, so the only way is to keep the whole string as one piece.

Example 3

Input: s = "aba"

Output: [[a, b, a], [aba]]

aba is a palindrome, so the whole string can be one piece. It can also be cut into a, b and a.

Constraints

• 1 ≤ s.length ≤ 16
• `s` contains only lowercase English letters.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each piece must be a palindrome. Do I need to check the whole string, or only the piece I am cutting off?
2.
The answer is every valid way to cut. At the start of the string, what are my choices?
3.
After I cut the first piece, what is left? Is that rest the same kind of problem?
4.
For aab, how many places can I cut? How many cut sets is that in total?
5.
If two different ways of cutting reach the same position, do I need to check the same piece twice?

Brute force approach

Idea

A string of length n has n − 1 gaps. Each gap is cut or not, so there are 2^(n−1) cut sets. For each cut set, split the string and check every piece. Keep a cut set only if every piece is a palindrome.

Thinking process

1
A cut set is decided by which gaps get a cut. So we can list every cut set by counting through all the gap choices.
2
For aab there are 2 gaps, so there are 2² = 4 cut sets.
3
No cut: the piece is aab, which is not a palindrome, so reject it.
4
Cut after the first letter: the pieces are a and ab. ab fails, so reject it.
5
Cut after the second letter: the pieces are aa and b. Both pass, so keep it.
6
Cut at both gaps: the pieces are a, a and b. All pass, so keep it. That gives 2 answers.

Visual

The cuts track shows a bar (|) at each cut of the current cut set. Green = a piece that passed. The shaded piece is the one being checked: blue if it is a palindrome, red if not. Brute force checks each piece again for every cut set that contains it.

Try every cut sets = "aab"step 1/15

cuts

This cut set (#0)

cut after s[0]: no
cut after s[1]: no
pieces: "aab"
palindrome checks so far: 0

answers

none yet

Cut set #0: pieces "aab"

Brute force builds this cut set from scratch, even if an earlier piece already fails.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> out;
        // Bit g of mask means "cut after s[g]". There are n - 1 gaps, so 2^(n-1) cut sets.
        for (int mask = 0; mask < (1 << (n - 1)); mask++) {
            vector<string> pieces;
            string cur;
            bool ok = true;
            for (int i = 0; i < n && ok; i++) {
                cur += s[i];
                bool cutHere = (i == n - 1) || ((mask >> i) & 1);
                if (cutHere) {
                    if (!isPal(cur)) ok = false;   // one bad piece rejects the whole cut set
                    else { pieces.push_back(cur); cur.clear(); }
                }
            }
            if (ok) out.push_back(pieces);
        }
        return out;
    }
private:
    bool isPal(const string& t) {
        int l = 0, r = (int)t.size() - 1;
        while (l < r) {
            if (t[l] != t[r]) return false;
            l++;
            r--;
        }
        return true;
    }
};

Complexity

Time O(N · 2^(N−1))Space O(N)

Each cut set costs O(N) to split and check, because its pieces have total length N. There are 2^(N−1) cut sets, so the work doubles with every extra letter. At N = 16 that is 32,768 cut sets, which is fast enough here. The output list is not counted in the space.

Better approach

Why brute force is slow

Brute force builds every cut set in full, then checks it. A cut set with a bad first piece is still built and checked to the end.

What repeated work are we doing?

The same piece is checked again and again. For aab, the piece a at the front is checked in two cut sets: the one that cuts after the first letter and the one that cuts after both letters.

What information can we reuse?

Choose the pieces from left to right. A piece is checked when it is chosen, and a bad piece stops its branch before anything is built below it.

New approach

Idea

Build the cuts one piece at a time. From start, try every end. Check only the piece s[start..end]. If it is a palindrome, cut it off and recurse from end + 1. If it is not, skip it, so nothing is built on top of a bad piece.

Thinking process

1
Brute force builds a whole cut set before it checks anything. Most cut sets fail at their first piece, but they are still built.
2
Instead, choose the first piece, then the second, and so on. Stop a branch as soon as one piece fails.
3
On aab from start 0: try a, a palindrome, so recurse from 1. Try aa, a palindrome, so recurse from 2. Try aab, not a palindrome, so skip it.
4
When the recursion reaches the end of the string, the path is one answer. Remove the last piece and try the next end.

Code & Implementation

better.cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> out;
        vector<string> path;               // the pieces chosen so far
        dfs(0, s, path, out);
        return out;
    }
private:
    // start = where the next piece begins. Try every end, but recurse only on palindromes.
    void dfs(int start, const string& s, vector<string>& path, vector<vector<string>>& out) {
        if (start == (int)s.size()) {      // every letter is covered by palindrome pieces
            out.push_back(path);
            return;
        }
        for (int end = start; end < (int)s.size(); end++) {
            if (!isPal(s, start, end)) continue;   // check only the piece being cut
            path.push_back(s.substr(start, end - start + 1));
            dfs(end + 1, s, path, out);
            path.pop_back();                       // undo, so the next end starts clean
        }
    }
    bool isPal(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
};

Complexity

Time O(N² · 2^N)Space O(N)

Each call tries up to N ends, and each check costs up to O(N). There can be about 2^N calls. The worst case is a string of one letter repeated, where every cut set works, so the output itself has 2^(N−1) answers. The pruning helps most when many pieces fail. O(N² · 2^N) is the worst case. The output list is not counted in the space.

Optimized approach

Idea

Start from brute force

Brute force checks each piece from scratch in every cut set. Backtracking checks a piece only when it is chosen, so a bad piece stops its branch. The table then makes each piece check O(1).

Find the repeated work

Backtracking still checks the same substring from many routes. For aaaa, the substring s[2..3] (aa) is checked once from each route that reaches start 2: a | a | and aa |. The table answers it in O(1), and it is computed only once.

Define the state — what variables do I need?

isPal[i][j]: True when `s[i..j]` is a palindrome. Filled once, from the inside out, for every i ≤ j.
start: Where the next piece begins. Everything before `start` is already cut into palindromes.
path: The pieces chosen so far. Pushed on the way down, popped on the way back up.

Define validity

Every piece must be a palindrome, so the search cuts s[start..end] only when isPal[start][end] is true. The table answers that in O(1), so no letter is compared again during the search.

Define the transitions — when does each pointer move, and why is it safe?

Before the search

For i from n − 1 down to 0, and j from i up to n − 1: isPal[i][j] = (s[i] == s[j]) and (j − i < 2 or isPal[i+1][j−1])

Row i + 1 is finished before row i, so isPal[i+1][j−1] is ready whenever it is read.

For each end from start to n − 1, if isPal[start][end] is true

Push `s[start..end]`, recurse from end + 1, then pop

The piece is a palindrome, so this branch is valid. Popping restores the path for the next end.

start == n

Copy `path` into the answers

Every letter is covered by palindrome pieces, so path is one valid way to cut s.

What does the current window add to the answer?

A complete path (start reached n) is one answer, so it is copied into the answers. Nothing else changes the answer list.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // isPal[i][j] = s[i..j] is a palindrome. Fill it from the inside out:
        // i runs from the end back to the start, so s[i+1..j-1] is ready before we need it.
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1]);
            }
        }
        vector<vector<string>> out;
        vector<string> path;
        dfs(0, s, isPal, path, out);
        return out;
    }
private:
    void dfs(int start, const string& s, const vector<vector<bool>>& isPal,
             vector<string>& path, vector<vector<string>>& out) {
        if (start == (int)s.size()) {
            out.push_back(path);
            return;
        }
        for (int end = start; end < (int)s.size(); end++) {
            if (!isPal[start][end]) continue;      // O(1) lookup instead of re-checking the letters
            path.push_back(s.substr(start, end - start + 1));
            dfs(end + 1, s, isPal, path, out);
            path.pop_back();
        }
    }
};

Complexity

Time O(N² + N · 2^N)Space O(N²)

The table takes O(N²) time and space. Each piece check now costs O(1) instead of O(N). The search still tries up to N ends per call, so the worst case is O(N · 2^N), the same as the number of answers when every cut set works. O(N²) is the palindrome table. The output list is not counted in the space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try all 2^(n−1) cut sets and keep one only if every piece is a palindrome	O(N · 2^(N−1))	O(N)
Better	Recurse only on palindrome pieces, so a bad piece is never built on	O(N² · 2^N)	O(N)
Optimal	Fill a palindrome table in O(N²); the search then checks each piece in O(1)	O(N² + N · 2^N)	O(N²)

Why does this belong to this pattern?

Clues in the problem statement

“every piece is a palindrome”The rule is checked on each piece, so a bad piece can stop its branch right away.
“find every way to cut”The answer is a list of all valid cut sets, so every valid route must be kept, not just one count.
“string”The choices are cut points. After a cut, the rest of the string is the same problem, only shorter.

Cut at every valid position+recurse on the rest+check each piece as a palindrome+undo the piece after the call→Backtracking → String partitioning (cut and recurse on the rest)

This is the first string partitioning question. The decision is where each piece ends, and the rule is local: each piece is checked on its own, not the whole string at once. That is different from Valid Palindrome, which checks the whole string once. The next two questions keep the same cut-and-recurse shape, but the rule changes: Restore IP Addresses checks the value and format of each part, and Word Break II checks each piece against a dictionary.

Don't make this mistake

Pattern confusion: checking the whole remainder instead of the piece

✗ if (!isPal(s, start, (int)s.size() - 1)) continue; // checks the rest of the string

✓ if (!isPal(s, start, end)) continue; // checks only the piece being cut

This treats the problem like Valid Palindrome: one check on the whole remainder. On aab, the remainder from start 0 is aab, which is not a palindrome. So every end is skipped, and the answer is [] instead of [[a, a, b], [aa, b]].

Forgetting to pop the piece after the call

✗ path.push_back(s.substr(start, end - start + 1)); dfs(end + 1, s, path, out); // no pop_back

✓ path.push_back(s.substr(start, end - start + 1)); dfs(end + 1, s, path, out); path.pop_back();

The piece a from the first cut stays in path when the search moves on. On aab, the pieces a, a, b are left in place, so the second answer becomes [a, a, b, aa, b]. Its pieces spell aabaab, not aab.

Filling the isPal table in the wrong order

✗ for (int i = 0; i < n; i++) for (int j = i; j < n; j++) isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1]);

✓ for (int i = n - 1; i >= 0; i--) for (int j = i; j < n; j++) isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i + 1][j - 1]);

isPal[i+1][j−1] must be filled before isPal[i][j] reads it. With i going up, row i + 1 is still all false. On aaa, isPal[0][2] reads isPal[1][1] too early, gets false, and the answer misses [aaa].

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture