Palindrome Partitioning

Description

Given a string s, partition it such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome is a string that reads the same forward and backward (e.g., "aba", "aa", "a").

A partition of a string means splitting the string into one or more non-empty contiguous substrings that together cover the entire original string.

For example, the string "aab" can be partitioned as ["a","a","b"] or ["a","ab"] or ["aa","b"] or ["aab"]. Among these, ["a","a","b"] and ["aa","b"] are palindrome partitions because every piece is a palindrome.

You must return all such palindrome partitions — not just one, not just the count, but every valid way to split the string so that each piece reads the same forwards and backwards.

Examples

Example 1

Input: s = "aab"

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

Explanation: There are exactly 4 ways to partition "aab":

["aab"] — "aab" is not a palindrome (reversed: "baa") ✗
["a","ab"] — "ab" is not a palindrome ✗
["aa","b"] — "aa" is a palindrome ✓, "b" is a palindrome ✓ → VALID
["a","a","b"] — all single characters are palindromes ✓ → VALID

So we return the 2 valid partitions.

Example 2

Input: s = "a"

Output: [["a"]]

Explanation: A single character is always a palindrome. There is only one way to partition a single-character string: ["a"].

Example 3

Input: s = "aba"

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

Explanation: The string "aba" itself is a palindrome, so ["aba"] is one valid partition. We can also split it into all single characters ["a","b","a"], each of which is a palindrome. The partition ["a","ba"] fails because "ba" is not a palindrome, and ["ab","a"] fails because "ab" is not a palindrome.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward approach is to generate every possible way to partition the string, then check each partition to see if all its pieces are palindromes.

Think of it like a string of beads with n-1 possible cutting points between consecutive beads. Each cutting point can either be cut or left intact. That gives us 2^(n-1) possible ways to split the string. We generate all of them, then filter out the ones where every piece is a palindrome.

For a string of length 3 like "aab", there are 2 possible cut positions (after index 0 and after index 1), giving 2² = 4 partitions. We check each one and keep only the valid palindrome partitions.

Step-by-Step Explanation

Let's trace through with s = "aab":

For n = 3, there are 2 cut positions → 2² = 4 possible partitions.

Step 1: Partition with no cuts (mask 00): ["aab"]. Check: is "aab" a palindrome? Reverse is "baa" ≠ "aab". NOT a palindrome. INVALID.

Step 2: Partition with cut after index 0 (mask 01): ["a", "ab"]. Check "a" → palindrome ✓. Check "ab" → reverse is "ba" ≠ "ab". NOT palindrome. INVALID.

Step 3: Partition with cut after index 1 (mask 10): ["aa", "b"]. Check "aa" → reverse is "aa" = "aa" ✓. Check "b" → single char ✓. ALL palindromes! VALID.

Step 4: Partition with cuts after both (mask 11): ["a", "a", "b"]. Check "a" ✓, "a" ✓, "b" ✓. All single chars are palindromes. VALID.

Step 5: Result: [["aa","b"], ["a","a","b"]]. We checked all 4 partitions and found 2 valid ones.

Brute Force — Testing All 4 Possible Partitions of "aab" — Watch how we generate all possible ways to split the string using cut positions, then check whether every piece in each partition is a palindrome.

Algorithm

For each bitmask from 0 to 2^(n-1) - 1:
- Interpret the bitmask as cut decisions: bit i = 1 means cut after index i
- Generate the partition pieces based on these cuts
- For each piece, check if it is a palindrome
- If ALL pieces are palindromes, add this partition to the result
Return the result list

Code

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> result;

        for (int mask = 0; mask < (1 << (n - 1)); mask++) {
            vector<string> parts;
            int start = 0;
            for (int i = 0; i < n - 1; i++) {
                if (mask & (1 << i)) {
                    parts.push_back(s.substr(start, i + 1 - start));
                    start = i + 1;
                }
            }
            parts.push_back(s.substr(start));

            bool valid = true;
            for (const string& p : parts) {
                int l = 0, r = p.size() - 1;
                while (l < r) {
                    if (p[l] != p[r]) { valid = false; break; }
                    l++; r--;
                }
                if (!valid) break;
            }
            if (valid) result.push_back(parts);
        }
        return result;
    }
};

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
        result = []

        for mask in range(1 << (n - 1)):
            parts = []
            start = 0
            for i in range(n - 1):
                if mask & (1 << i):
                    parts.append(s[start:i + 1])
                    start = i + 1
            parts.append(s[start:])

            if all(p == p[::-1] for p in parts):
                result.append(parts)

        return result

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>> result = new ArrayList<>();

        for (int mask = 0; mask < (1 << (n - 1)); mask++) {
            List<String> parts = new ArrayList<>();
            int start = 0;
            for (int i = 0; i < n - 1; i++) {
                if ((mask & (1 << i)) != 0) {
                    parts.add(s.substring(start, i + 1));
                    start = i + 1;
                }
            }
            parts.add(s.substring(start));

            boolean valid = true;
            for (String p : parts) {
                String rev = new StringBuilder(p).reverse().toString();
                if (!p.equals(rev)) { valid = false; break; }
            }
            if (valid) result.add(parts);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

We iterate over all 2^(n-1) possible bitmasks. For each bitmask, we generate the partition in O(n) time and then check whether all pieces are palindromes. Since the total length of all pieces in any partition sums to n, each palindrome check takes O(n) total. Combined: 2^(n-1) partitions × O(n) work each = O(n × 2^n).

With n ≤ 16, this is at most 16 × 2^16 ≈ 1,048,576 operations — feasible, but wasteful because most partitions contain at least one non-palindromic piece.

Space Complexity: O(n × 2^n)

In the worst case (all characters identical like "aaaa"), every partition is valid. There are 2^(n-1) partitions, and each partition stored as a list of strings totals O(n) space. Result storage: O(n × 2^n). Auxiliary space for a single partition: O(n).

Why This Approach Is Not Efficient

The brute force approach generates every possible partition regardless of validity, then retroactively checks palindrome conditions. This is wasteful because:

No early termination: Even if the first piece of a partition is not a palindrome, we still generate the entire partition before discovering it is invalid. For example, partition ["ab", ...] will fail because "ab" is not a palindrome, but we wastefully construct the remaining pieces.
Redundant work: The same substring is checked for palindromicity multiple times across different partitions. For instance, "a" at position 0 appears in multiple partitions and is checked each time.

Key insight: Instead of generating all partitions blindly, we can build partitions incrementally. At each position, we try extending the current piece. If the piece so far is a palindrome, we recurse to partition the remainder. If not, we immediately abandon that path. This backtracking strategy prunes invalid branches before they are fully explored, dramatically reducing wasted work.

Better Approach - Backtracking with Pruning

Intuition

Instead of generating all partitions and filtering, we build valid partitions step by step using backtracking.

Imagine you are reading the string left to right. At each position, you consider all possible substrings that start here. If a substring is a palindrome, you "accept" it as one piece of the partition and move on to partition the rest of the string. If the substring is NOT a palindrome, you skip it entirely — there is no point exploring further because any partition containing a non-palindromic piece is automatically invalid.

This is like navigating a maze where you immediately turn back at dead ends instead of walking the entire maze before checking if you reached the exit.

The key difference from brute force: we check palindromes during construction, not after. This lets us prune entire branches of the search tree early.

Step-by-Step Explanation

Let's trace through with s = "aab":

Step 1: Start at index 0 with empty path []. We try all substrings starting at index 0.

Step 2: Try s[0..0] = "a". Is "a" a palindrome? Yes (single char). Add "a" to path → ["a"]. Recurse from index 1.

Step 3: At index 1 with path ["a"]. Try s[1..1] = "a". Palindrome? Yes. Path → ["a","a"]. Recurse from index 2.

Step 4: At index 2 with path ["a","a"]. Try s[2..2] = "b". Palindrome? Yes. Path → ["a","a","b"]. Recurse from index 3.

Step 5: Index 3 equals string length! We partitioned the entire string. Add ["a","a","b"] to result.

Step 6: Backtrack to index 1. Try s[1..2] = "ab". Is "ab" a palindrome? No! (a ≠ b). PRUNE — do not recurse. This saves us from exploring all partitions containing "ab" as a piece.

Step 7: Backtrack to index 0. Try s[0..1] = "aa". Is "aa" a palindrome? Yes! Path → ["aa"]. Recurse from index 2.

Step 8: At index 2 with path ["aa"]. Try s[2..2] = "b". Palindrome? Yes. Path → ["aa","b"]. Recurse from index 3.

Step 9: Index 3 == length! Add ["aa","b"] to result.

Step 10: Backtrack to index 0. Try s[0..2] = "aab". Palindrome? No! (a ≠ b). PRUNE.

Step 11: All options from index 0 exhausted. Result: [["a","a","b"], ["aa","b"]].

Backtracking — Exploring Only Palindromic Prefixes — Watch how backtracking builds partitions incrementally, only branching on palindromic substrings and immediately pruning non-palindromic paths.

Algorithm

Create a helper function backtrack(start, path):
- If start equals the string length, add a copy of path to the result
- For end from start to n-1:
  - If s[start..end] is a palindrome:
    - Add s[start..end] to path
    - Recursively call backtrack(end + 1, path)
    - Remove the last element from path (backtrack)
Call backtrack(0, []) and return the collected result

Code

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, path, result);
        return result;
    }

private:
    void backtrack(string& s, int start, vector<string>& path,
                   vector<vector<string>>& result) {
        if (start == (int)s.size()) {
            result.push_back(path);
            return;
        }
        for (int end = start; end < (int)s.size(); end++) {
            if (isPalindrome(s, start, end)) {
                path.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, path, result);
                path.pop_back();
            }
        }
    }

    bool isPalindrome(string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        result = []

        def backtrack(start: int, path: list[str]):
            if start == len(s):
                result.append(path[:])
                return
            for end in range(start, len(s)):
                substring = s[start:end + 1]
                if substring == substring[::-1]:
                    path.append(substring)
                    backtrack(end + 1, path)
                    path.pop()

        backtrack(0, [])
        return result

class Solution {
    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()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

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

Complexity Analysis

Time Complexity: O(n × 2^n)

In the worst case (all characters identical, e.g., "aaaa"), every substring is a palindrome, so no pruning occurs. The recursion tree has up to 2^(n-1) leaf nodes (one for each valid partition), and copying each partition to the result takes O(n). Additionally, at each recursive call, checking whether a substring is a palindrome takes O(n) in the worst case. Overall: O(n × 2^n).

However, for typical inputs with mixed characters, the pruning dramatically reduces the number of nodes explored. This is the practical advantage over brute force.

Space Complexity: O(n)

The recursion depth is at most n (one level per character). The current path stores at most n strings. Not counting the output, auxiliary space is O(n).

Why This Approach Is Not Efficient

The backtracking approach prunes well, but every palindrome check during the recursion scans the substring character by character, taking O(length) time per check. For a string of length 16, at each recursive call we may check multiple substrings of varying lengths, and the same substring pair (i, j) might be checked for palindromicity across different branches of the recursion tree.

For instance, when backtracking from index 5 to index 9, we check isPalindrome(s, 5, 9). If another branch also reaches index 5, it checks the same substring again. These redundant palindrome checks waste time.

Key insight: We can precompute whether every substring s[i..j] is a palindrome using dynamic programming in O(n²) time and store the results in a lookup table. Then during backtracking, each palindrome check becomes an O(1) table lookup instead of an O(n) scan. This eliminates all redundant palindrome computations.

Optimal Approach - Backtracking with DP Palindrome Cache

Intuition

The optimal approach combines two techniques:

DP palindrome precomputation: Build a 2D boolean table isPal[i][j] where isPal[i][j] = true if the substring s[i..j] is a palindrome. This table is filled using the recurrence: s[i..j] is a palindrome if s[i] == s[j] AND the inner substring s[i+1..j-1] is also a palindrome (or the substring has length ≤ 2).
Backtracking with O(1) lookups: Use the same backtracking logic as before, but instead of calling a two-pointer palindrome checker each time, simply look up isPal[start][end] in constant time.

Think of it like preparing a cheat sheet before an exam. Instead of re-deriving palindrome checks during the recursion (the exam), you pre-calculate all answers (the cheat sheet) and just look them up instantly.

Step-by-Step Explanation

Let's trace through with s = "aab":

Phase 1: Build the isPal table (O(n²) preprocessing)

Step 1: Initialize: isPal is a 3×3 table, all false.

Step 2: Base case — every single character is a palindrome: isPal[0][0] = true ("a"), isPal[1][1] = true ("a"), isPal[2][2] = true ("b").

Step 3: Length 2 substrings: isPal[0][1] checks s[0..1] = "aa". s[0]='a' == s[1]='a'? Yes, and length is 2 → isPal[0][1] = true.

Step 4: isPal[1][2] checks s[1..2] = "ab". s[1]='a' == s[2]='b'? No → isPal[1][2] = false.

Step 5: Length 3 substring: isPal[0][2] checks s[0..2] = "aab". s[0]='a' == s[2]='b'? No → isPal[0][2] = false.

Step 6: Table complete. Palindromic substrings: "a"(0,0), "a"(1,1), "b"(2,2), "aa"(0,1).

Phase 2: Backtracking with O(1) lookups

Step 7: bt(0, []): Check isPal[0][0]=true → "a" is palindrome → recurse bt(1, ["a"]).

Step 8: bt(1, ["a"]): Check isPal[1][1]=true → "a" → recurse bt(2, ["a","a"]). Then bt(2, ["a","a"]): isPal[2][2]=true → "b" → bt(3) → FOUND ["a","a","b"].

Step 9: Back at bt(1): Check isPal[1][2]=false → "ab" is NOT palindrome. O(1) instant rejection — no character scanning needed!

Step 10: Back at bt(0): Check isPal[0][1]=true → "aa" → recurse. bt(2, ["aa"]): isPal[2][2]=true → "b" → bt(3) → FOUND ["aa","b"].

Step 11: Back at bt(0): Check isPal[0][2]=false → "aab" rejected. Done. Result: [["a","a","b"], ["aa","b"]].

DP Palindrome Table — Precomputing All Palindromic Substrings — Watch how we build a lookup table that tells us instantly whether any substring s[i..j] is a palindrome, eliminating redundant O(n) checks during backtracking.

Algorithm

Phase 1: Precompute Palindrome Table

Create an n×n boolean table isPal, initialized to false
Fill the diagonal: isPal[i][i] = true for all i (single characters)
For each substring length from 2 to n:
- For each starting index i (with ending index j = i + length - 1):
  - If s[i] == s[j] AND (length == 2 OR isPal[i+1][j-1] is true):
    - Set isPal[i][j] = true

Phase 2: Backtrack with O(1) Lookups

Create a helper function backtrack(start, path):
- If start equals n, add a copy of path to result
- For end from start to n-1:
  - If isPal[start][end] is true (O(1) lookup):
    - Add s[start..end] to path, recurse, then remove (backtrack)
Call backtrack(0, []) and return result

Code

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n, false));

        // Precompute palindrome table
        for (int i = 0; i < n; i++) isPal[i][i] = true;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    isPal[i][j] = (len == 2) || isPal[i + 1][j - 1];
                }
            }
        }

        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, isPal, path, result);
        return result;
    }

private:
    void backtrack(string& s, int start, vector<vector<bool>>& isPal,
                   vector<string>& path, vector<vector<string>>& result) {
        if (start == (int)s.size()) {
            result.push_back(path);
            return;
        }
        for (int end = start; end < (int)s.size(); end++) {
            if (isPal[start][end]) {
                path.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, isPal, path, result);
                path.pop_back();
            }
        }
    }
};

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
        is_pal = [[False] * n for _ in range(n)]

        # Precompute palindrome table
        for i in range(n):
            is_pal[i][i] = True
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    is_pal[i][j] = (length == 2) or is_pal[i + 1][j - 1]

        result = []

        def backtrack(start: int, path: list[str]):
            if start == n:
                result.append(path[:])
                return
            for end in range(start, n):
                if is_pal[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1, path)
                    path.pop()

        backtrack(0, [])
        return result

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];

        // Precompute palindrome table
        for (int i = 0; i < n; i++) isPal[i][i] = true;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    isPal[i][j] = (len == 2) || isPal[i + 1][j - 1];
                }
            }
        }

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

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

Complexity Analysis

Time Complexity: O(n² + n × 2^n)

The preprocessing phase builds the isPal table in O(n²) time by iterating over all O(n²) substrings and filling each cell in O(1) using previously computed results.

The backtracking phase, in the worst case, visits up to 2^(n-1) valid partitions. For each partition, copying to the result takes O(n). At each recursive call, the palindrome check is O(1) (table lookup) instead of O(n), and we iterate over at most n choices. Combined: O(n × 2^n).

Total: O(n²) + O(n × 2^n) = O(n × 2^n). The preprocessing cost is dwarfed by the backtracking cost. However, the practical improvement is significant: individual palindrome checks drop from O(n) to O(1), which removes redundant work in branches that check the same substrings.

With n ≤ 16: preprocessing = 256 operations, backtracking ≤ 16 × 65,536 ≈ 1M operations.

Space Complexity: O(n²)

The isPal table uses O(n²) space. The recursion stack depth is at most O(n). The current path uses O(n) space. Dominant: O(n²) for the DP table (excluding output).

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Palindrome Partitioning

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Backtracking with Pruning

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Backtracking with DP Palindrome Cache

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis