Command Palette

Search for a command to run...

Hectal
Problem 13.8 · BacktrackingMedium

Palindrome Partitioning

PatternBacktrackingExpand Around Center

What it teaches: Backtracking over cut positions, choosing only cuts that leave a palindrome piece.

Practise it on judges as “Palindrome Partitioning”.

The problem

Split string s into pieces so that every piece is a palindrome. Return all such partitions.

Example 1

Input: s = "aab"
Output: [[a, a, b], [aa, b]]

Constraints

  • 1 ≤ s.length ≤ 16

Pattern clues in the wording

  • → "All ways to split"
  • → Each piece must satisfy a check

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "aab"
[["a","a","b"],["aa","b"]]
2
s = "a"
[["a"]]

From slow to fast

Approaches

1. Backtracking over cut points · O(n · 2ⁿ)
1

Backtracking over cut points

Time O(n · 2ⁿ) Space O(n)

dfs(start): if start == n record. For each end from start to n − 1, if s[start..end] is a palindrome, add it, recurse from end + 1, remove it.

Approach 1
import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> out = new ArrayList<>();
        dfs(s, 0, new ArrayList<>(), out);
        return out;
    }

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

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

Verdict: At most 2ⁿ⁻¹ partitions for n ≤ 16.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One character
  • All characters equal (many partitions)

Mistakes people make

  • Recording before the whole string is used.

Interview

Follow-up questions

How do you avoid re-checking the same substrings?