Palindrome Patterns

Palindrome Partitioning

Split a string into parts where every part is a palindrome. Use backtracking: at each position, try every prefix that's a palindrome, then recurse on the remainder.

O(n * 2^n)

O(n)

How It Works

Palindrome partitioning splits a string so every piece is a palindrome, enumerating all such splits with backtracking. At each starting index, try every prefix; if the prefix is a palindrome, add it to the current path and recurse on the remaining suffix, then remove it and try a longer prefix. Reaching the end of the string means the current path is one complete valid partition.

The output can be exponential — a string of identical characters has 2^(n−1) partitions — so exponential worst-case time is inherent. Precomputing an O(n²) DP table of isPalindrome(i, j) makes each palindrome check O(1) inside the recursion, which is the standard optimization over re-checking substrings character by character.

Step-by-Step Visualization

Partition 'aab' into palindromic substrings

Try'a' + partition('ab')

1/4

Code

Java

static List<List<String>> partition(String s) {
  List<List<String>> result = new ArrayList<>();
  backtrack(s, 0, new ArrayList<>(), result);
  return result;
}

static void backtrack(String s, int start, List<String> path, List<List<String>> result) {
  if (start == s.length()) { result.add(new ArrayList<>(path)); return; }
  for (int end = start; end < s.length(); end++) {
    if (isPalin(s, start, end)) {
      path.add(s.substring(start, end + 1));
      backtrack(s, end + 1, path, result);
      path.remove(path.size() - 1);
    }
  }
}

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

Tips & Gotchas

1Use backtracking: try every possible first palindrome, then recurse

2Pre-compute a palindrome lookup table for O(1) checks

3Each partition is a path in the recursion tree

Practice Problems

1Palindrome Partitioning
2Palindrome Partitioning II
3Restore IP Addresses
4Word Break II

About the Palindrome Patterns Pattern

A palindrome reads the same forwards and backwards. The core techniques: expand from the center outward to find palindromes, or use DP to check if substrings are palindromes.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

How does Palindrome Partitioning II differ from the enumeration version?

Partitioning II asks only for the minimum number of cuts, not every partition, so it swaps backtracking for dynamic programming: dp[i] is the fewest cuts for the prefix ending at i. That reframing drops the complexity from exponential to O(n²).

Why precompute a palindrome DP table before backtracking?

Without it, each prefix check costs O(n) inside an already-exponential recursion, and identical substrings get re-verified many times. A one-time O(n²) table makes every check O(1), which significantly trims the constant factor on large inputs.