☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Palindrome partitioning

Hard TUF ID 871 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string s. Partition it into contiguous pieces so that every piece is a palindrome, and return all such partitions. A partition is a list of substrings that, concatenated in order, rebuild s; the pieces must be non-empty. Any order of partitions is accepted; the methods below list them in the order their first cut appears, which is also the order LeetCode shows.

Constraints: 1 ≤ s.length ≤ 16, lowercase English letters.

Example 1

s = "aab"
answer = [["a", "a", "b"], ["aa", "b"]]
// "a|a|b" and "aa|b" work; "aab" and "a|ab" fail because "ab" and "aab" are not palindromes

Example 2

s = "abba"
answer = [["a", "b", "b", "a"], ["a", "bb", "a"], ["abba"]]

Example 3

s = "abc"
answer = [["a", "b", "c"]]    // single letters are always palindromes, so one partition always exists

Approach 1: Brute force, try every cut and check each piece from scratch

Intuition. A partition is a sequence of cuts, and the first piece must start at index 0. Choose where the first piece ends: for every end from start to n - 1, if s[start..end] is a palindrome, commit to it and solve the rest of the string, s[end + 1..], the same way. When start reaches n every character has been placed in some palindrome and the current list of pieces is one complete answer. Pieces that are not palindromes are rejected on the spot, so the recursion never explores a partition that would have to be thrown away later; this is backtracking with the validity test applied as early as possible.

Each candidate piece is checked with a fresh two-pointer scan, which is the only wasteful part: the same substring is tested again and again from different partial partitions.

Algorithm.

  1. cutRec(start, cur): if start == n, record a copy of cur and return.
  2. For end = start .. n - 1: if s[start..end] is a palindrome, append it, recurse with end + 1, remove it.
  3. isPalindrome(lo, hi) walks inward from both ends comparing characters.
static List<List<String>> bruteForce(String s) {
    List<List<String>> out = new ArrayList<>();
    cutRec(s, 0, new ArrayList<>(), out);
    return out;
}

static void cutRec(String s, int start, List<String> cur, List<List<String>> out) {
    if (start == s.length()) {                       // every character has been placed in some palindrome
        out.add(new ArrayList<>(cur));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) {
            cur.add(s.substring(start, end + 1));
            cutRec(s, end + 1, cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

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

Dry run on s = "aab":

start cur end tried piece palindrome?
0 [] 0 “a” yes → recurse
1 [“a”] 1 “a” yes → recurse
2 [“a”, “a”] 2 “b” yes → start = 3, record [“a”, “a”, “b”]
1 [“a”] 2 “ab” no
0 [] 1 “aa” yes → recurse
2 [“aa”] 2 “b” yes → record [“aa”, “b”]
0 [] 2 “aab” no

Complexity. Time O(2^n · n): there are n - 1 gaps between characters and each is either cut or not, so up to 2^(n-1) partitions exist (all of them valid when s is a single repeated letter), and each partition costs O(n) to check its pieces and O(n) to copy. Space O(n) for the recursion stack and the working list, beyond the output.

Approach 2: Optimal, precompute palindromes with interval DP

Intuition. Whether s[i..j] is a palindrome does not depend on the partition we are building, so compute it once for all O(n^2) substrings and answer every later question in O(1). The recurrence is the classic one: s[i..j] is a palindrome when its end characters match and the inside s[i+1..j-1] is a palindrome (or is empty or a single character, when j - i < 2). Filling i from n - 1 down to 0 and j from i upward guarantees pal[i + 1][j - 1] is ready before it is read.

The backtracking is then identical to the brute force except that the palindrome test is a table lookup. On inputs like "aaaa...a", where every substring is a palindrome and every cut pattern is valid, the recursion still has to produce 2^(n-1) answers, so the exponential part cannot be removed; what the table removes is the extra O(n) factor spent re-scanning the same substrings.

Algorithm.

  1. Allocate pal[n][n]. For i = n - 1 .. 0, for j = i .. n - 1: pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]).
  2. Run the same cut recursion, testing pal[start][end] instead of scanning.
static List<List<String>> optimal(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
        }
    }
    List<List<String>> out = new ArrayList<>();
    cutRecDp(s, 0, pal, new ArrayList<>(), out);
    return out;
}

static void cutRecDp(String s, int start, boolean[][] pal, List<String> cur, List<List<String>> out) {
    if (start == s.length()) {
        out.add(new ArrayList<>(cur));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (pal[start][end]) {
            cur.add(s.substring(start, end + 1));
            cutRecDp(s, end + 1, pal, cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

The table for "abba":

i \ j 0 (a) 1 (b) 2 (b) 3 (a)
0 T F F T
1   T T F
2     T F
3       T

pal[0][3] is true because s[0] == s[3] and pal[1][2] is true; pal[1][2] is true because s[1] == s[2] and the inside is empty (j - i = 1 < 2).

Complexity. Time O(n^2) to fill the table plus O(2^n · n) for the enumeration in the worst case, with the n factor now coming only from copying each answer. Space O(n^2) for the table and O(n) for the recursion, beyond the output.

Why not memoise the partitions themselves?

A tempting third variant stores, for every start, the list of all partitions of the suffix s[start..], so that partitions(start) concatenates piece + partitions(end + 1) for every palindromic piece. It avoids re-walking the recursion tree but has to copy whole lists of lists at every level, so its total work is still proportional to the output size times n, and it uses far more memory than the backtracking. When the required output is all partitions, the backtracking above is already output-optimal up to the copy factor. Memoisation pays off only in the counting and minimum cuts variants, where the answer is a number instead of a list; those are linked below.

Edge cases and pitfalls