Palindrome Partitioning

Medium Recursion & Backtracking Choice per Position Original on LeetCode

Reported atMicrosoft

Palindrome Partitioning is a medium recursion & backtracking problem solved with the choice per position pattern. The best approach, optimal (palindrome dp table + backtracking), runs in O(n · 2^n) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking with a direct palindrome check) up.

Problem

Given a string s, cut it into consecutive pieces so that every piece is a palindrome (reads the same forwards and backwards). Return every such way of cutting s, each as the list of its pieces in order.

The partitions may be returned in any order.

Examples

Example 1

Input
s = "noon"
Output
[["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]]
Why
Every single letter is a palindrome, "oo" is one in the middle, and the whole word reads the same both ways.

Example 2

Input
s = "abc"
Output
[["a", "b", "c"]]
Why
No piece longer than one letter is a palindrome, so only the split into single letters works.

Example 3

Input
s = "z"
Output
[["z"]]
Why
A one-letter string has exactly one partition.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (backtracking with a direct palindrome check)O(n · 2^n)O(n)
Optimal (palindrome DP table + backtracking)O(n · 2^n)O(n²)

1Brute force (backtracking with a direct palindrome check)

TimeO(n · 2^n)There are up to 2^(n-1) partitions; building each and checking its pieces costs O(n).
SpaceO(n)Recursion depth and the current list are at most n (the output itself is not counted).

From a start index, try every end index. If s[start..end] is a palindrome (checked with two pointers), add it to the current list and recurse from end + 1. When start reaches the end of the string, the current list is one valid partition.

  1. dfs(start): if start == n, copy the current list into the answer.
  2. For end from start to n-1: if isPalindrome(start, end), add s[start..end], call dfs(end + 1), remove it.
  3. isPalindrome walks two pointers inwards.
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        dfs(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(String s, int start, List<String> cur, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!isPalindrome(s, start, end)) continue;
            cur.add(s.substring(start, end + 1));
            dfs(s, end + 1, cur, res);
            cur.remove(cur.size() - 1);
        }
    }

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

2Optimal (palindrome DP table + backtracking)

TimeO(n · 2^n)Filling the table is O(n²); the search still emits up to 2^(n-1) partitions of O(n) total length each, but every palindrome test is now O(1).
SpaceO(n²)The n × n table, plus O(n) recursion depth.

The backtracking is unavoidable because the answer itself can have 2^(n-1) partitions, but the palindrome checks can be made O(1). Fill a table isPal[i][j] from the end of the string backwards: s[i..j] is a palindrome when its ends match and the inside s[i+1..j-1] is a palindrome (or is empty or one letter). The search then only looks up the table.

  1. For i from n-1 down to 0 and j from i to n-1: isPal[i][j] = s[i] == s[j] && (j - i < 2 || isPal[i+1][j-1]).
  2. dfs(start): at start == n record a copy of the current list.
  3. For each end with isPal[start][end], add the piece, recurse from end + 1, remove it.
class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        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]);
            }
        }
        List<List<String>> res = new ArrayList<>();
        dfs(s, 0, isPal, new ArrayList<>(), res);
        return res;
    }

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

Edge cases to test

  • A single character
  • All characters equal (every one of the 2^(n-1) splits is valid)
  • No repeated neighbours or mirrors (only the all-single-letters split)
  • The whole string is a palindrome

Hints

Hint 1

Decide the first piece: it must be a palindrome s[0..j]. Then the rest of the string is the same problem starting at j + 1.

Hint 2

Backtracking: keep the pieces chosen so far in a list, add a palindromic piece, recurse, then remove it.

Hint 3

The same substring is checked many times. Precompute isPal[i][j] once with DP: s[i] == s[j] and (j - i < 2 or isPal[i+1][j-1]).

FAQ

What is the best time complexity for Palindrome Partitioning?

Optimal (palindrome DP table + backtracking) runs in O(n · 2^n) time and O(n²) extra space. Filling the table is O(n²); the search still emits up to 2^(n-1) partitions of O(n) total length each, but every palindrome test is now O(1).

Which pattern does Palindrome Partitioning use?

It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.

Is there a brute force solution for Palindrome Partitioning?

Yes. Brute force (backtracking with a direct palindrome check) takes O(n · 2^n) time and O(n) space. From a start index, try every end index.

Which edge cases should I test for Palindrome Partitioning?

A single character; All characters equal (every one of the 2^(n-1) splits is valid); No repeated neighbours or mirrors (only the all-single-letters split); The whole string is a palindrome.