77.Palindrome Partitioning

MediumBacktracking · 7/9

Problem

Given a string s, split it into pieces so that every piece is a palindrome, and return all such partitions.

A partition is a list of substrings that, concatenated in order, give back s. A single character is always a palindrome, so at least one partition always exists.

Examples

Input:  s = "aab"
Output: [["a","a","b"], ["aa","b"]]
Explanation: "aab" and "ab" are not palindromes, so only these two splits work.

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

Input:  s = "efe"
Output: [["e","f","e"], ["efe"]]

Constraints

1 <= s.length <= 16
s contains only lowercase English letters.

💡 Key Insight

Choose the first piece s[start..end]; if it is a palindrome, recursively partition the rest s[end+1..]. Every root-to-leaf path in this tree is one answer. The expensive part is the repeated palindrome check — precompute a table isPal[i][j] with DP (s[i] == s[j] and the inside isPal[i+1][j-1] is a palindrome) so each check is O(1).

Backtracking with Two-Pointer Check

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

Intuition

At position start, try every possible end end. Check s[start..end] with two pointers moving inward. If it is a palindrome, add it to path and recurse from end + 1. Reaching start == n means the whole string has been cut into palindromes.

Algorithm

dfs(start): if start == n, record a copy of path.
For end from start to n - 1:
- If isPalindrome(s, start, end): push s.substring(start, end + 1), dfs(end + 1), pop.

Visualization

flowchart TD
    R["start=0 'aab'"] -->|"'a' ✓"| A["start=1 'ab'"]
    R -->|"'aa' ✓"| B["start=2 'b'"]
    R -.->|"'aab' ✗"| X["pruned"]
    A -->|"'a' ✓"| A1["start=2 'b'"]
    A -.->|"'ab' ✗"| X2["pruned"]
    A1 -->|"'b' ✓"| A2["[a, a, b]"]
    B -->|"'b' ✓"| B1["[aa, b]"]

Code

java

import java.util.*;

class Solution {
    private final List<List<String>> result = new ArrayList<>();
    private final List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return result;
    }

    private void dfs(String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path)); // whole string partitioned
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                dfs(s, end + 1);
                path.remove(path.size() - 1);
            }
        }
    }

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

Complexity

Time: O(n · 2^n) — there are up to 2^(n-1) partitions (each gap is cut or not); each palindrome check and copy is O(n).
Space: O(n) — recursion depth and path (output excluded).

Backtracking with DP Palindrome TableOptimal

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

Intuition

The same substrings are checked again and again in different branches (e.g. "b" above is checked twice). Precompute isPal[i][j] once in O(n²): a substring is a palindrome if its end characters match and the part inside is a palindrome — or there is no real "inside" because the substring has length 1 or 2 (j - i < 2). Fill i from right to left so isPal[i+1][j-1] is ready when needed.

Algorithm

For i from n - 1 down to 0, for j from i to n - 1:
- isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i+1][j-1]).
Backtrack exactly as before, using isPal[start][end] as the O(1) check.

Visualization

s = "aab"    isPal[i][j]  (rows i, cols j)

        j=0   j=1   j=2
i=0      T     T     F      "a", "aa", "aab"
i=1      .     T     F      "a", "ab"
i=2      .     .     T      "b"

Code

java

import java.util.*;

class Solution {
    private final List<List<String>> result = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private boolean[][] isPal;

    public List<List<String>> partition(String s) {
        int n = s.length();
        isPal = new boolean[n][n];
        // fill from the bottom so isPal[i + 1][j - 1] is already known
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                isPal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || isPal[i + 1][j - 1]);
            }
        }
        dfs(s, 0);
        return result;
    }

    private void dfs(String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!isPal[start][end]) continue; // O(1) lookup
            path.add(s.substring(start, end + 1));
            dfs(s, end + 1);
            path.remove(path.size() - 1);
        }
    }
}

Complexity

Time: O(n · 2^n) — the output can contain 2^(n-1) partitions of total length n; the table adds only O(n²).
Space: O(n²) — the isPal table, plus O(n) recursion depth.

Complexity Comparison

Approach	Time	Space
Backtracking + two-pointer check	O(n · 2^n)	O(n)
Backtracking + DP table	O(n · 2^n), cheaper checks	O(n²)

Common Pitfalls

Off-by-one with substring(start, end + 1) — the end index of substring is exclusive.
Filling the DP table top-down by i — isPal[i+1][j-1] would not be computed yet. Iterate i from n - 1 to 0.
Forgetting the j - i < 2 base case, which reads isPal[i+1][i] (an empty/invalid range) for length-2 substrings.
Adding path instead of a copy to the result.