Palindrome Partitioning

mediumBacktracking80 stepsJava · Python · C++

Split a string into pieces that are all palindromes, returning every way. From position start, try each end i; if s[start..i] is a palindrome, take it and recurse on the rest. Reaching the end means one full partition.

▶ Watch the animated trace

Traced input: s = "aab" → [["a", "a", "b"], ["aa", "b"]]. Original problem: neetcode.io/problems/palindrome-partitioning

Complexity

BestO(n·2ⁿ)

AverageO(n·2ⁿ)

WorstO(n·2ⁿ)

SpaceO(n)

Up to 2ⁿ⁻¹ partitions; each palindrome check is O(n).

Key idea

Each recursion level chooses the next cut.
Only palindromic prefixes are worth exploring.
Precomputing a palindrome table makes each check O(1).

Common mistakes

Off-by-one with substring(start, i + 1).
Forgetting to copy the path into the result.

Solution

Java

List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    cut(s, 0, new ArrayList<>(), res);
    return res;
}

void cut(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < s.length(); i++) {
        if (!isPal(s, start, i)) {
            continue;
        }
        path.add(s.substring(start, i + 1));
        cut(s, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

boolean isPal(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

Python

def partition(s: str) -> List[List[str]]:
    res = []

    def cut(start: int, path: List[str]) -> None:
        if start == len(s):
            res.append(path[:])
            return
        for i in range(start, len(s)):
            piece = s[start:i + 1]
            if piece != piece[::-1]:
                continue
            path.append(piece)
            cut(i + 1, path)
            path.pop()

    cut(0, [])
    return res

C++

bool isPal(const string& s, int l, int r) {
    while (l < r) if (s[l++] != s[r--]) return false;
    return true;
}

void cut(const string& s, int start, vector<string>& path, vector<vector<string>>& res) {
    if (start == (int)s.size()) {
        res.push_back(path);
        return;
    }
    for (int i = start; i < (int)s.size(); i++) {
        if (!isPal(s, start, i)) {
            continue;
        }
        path.push_back(s.substr(start, i - start + 1));
        cut(s, i + 1, path, res);
        path.pop_back();
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> path;
    cut(s, 0, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single character One piece.	`s = "a"`	`[["a"]]`
All the same Every cut works.	`s = "aaa"`	`[["a", "a", "a"], ["a", "aa"], ["aa", "a"], ["aaa"]]`
No long palindromes Only single letters.	`s = "abc"`	`[["a", "b", "c"]]`