131. Palindrome Partitioning (Medium)
Problem
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings.
Example
s = "aab"→[["a","a","b"], ["aa","b"]]s = "a"→[["a"]]
LeetCode 131 · Link · Medium
Approach 1: Brute force, backtracking with per-cut palindrome check
For each cut point, check whether the left piece is a palindrome; if yes, recurse on the rest.
def partition(s): result = [] path = []
def is_pal(t): return t == t[::-1] # L1: O(k) slice + compare
def backtrack(start): if start == len(s): result.append(path[:]) # L2: O(n) copy at leaf return for end in range(start + 1, len(s) + 1): piece = s[start:end] # L3: O(k) slice if is_pal(piece): path.append(piece) # L4: O(1) push backtrack(end) # L5: recurse path.pop() # L6: O(1) pop
backtrack(0) return resultWhere the time goes, line by line
Variables: n = len(s), k = substring length.
| Line | Per-call cost | Times executed | Contribution |
|---|---|---|---|
| L1/L3 (palindrome check + slice) | O(k) per cut | O(n · 2^n) total cuts | O(n · 2^n) |
| L5 (recurse) | O(1) dispatch | O(2^n) nodes | O(2^n) ← dominates |
| L2 (copy) | O(n) | partitions | O(n · partitions) |
There are 2^(n-1) possible cut positions, so the search space is O(2^n). Each call to is_pal for a substring of length k costs O(k).
Complexity
- Time: O(n · 2^n). For each of 2^(n-1) possible partitions, O(n) palindrome checks.
- Space: O(n) recursion.
Approach 2: Two-pointer palindrome check (same Big-O, no string slicing)
Avoid slicing by checking the palindrome inline.
def partition(s): result = [] path = [] n = len(s)
def is_pal(l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 # L1: O(k) two-pointer check return True
def backtrack(start): if start == n: result.append(path[:]) # L2: O(n) copy return for end in range(start, n): if is_pal(start, end): path.append(s[start:end + 1]) # L3: O(k) slice for result backtrack(end + 1) # L4: recurse path.pop()
backtrack(0) return resultWhere the time goes, line by line
Variables: n = len(s), k = substring length.
| Line | Per-call cost | Times executed | Contribution |
|---|---|---|---|
| L1 (two-pointer check) | O(k) | O(n^2) pairs | O(n^2) setup |
| L4 (recurse) | O(1) dispatch | O(2^n) nodes | O(n · 2^n) ← dominates |
| L2 (copy) | O(n) | partitions | O(n · partitions) |
Complexity
- Time: O(n · 2^n) worst case.
- Space: O(n) recursion.
Approach 3: Precompute palindrome DP table (optimal constant factor)
Precompute is_pal[i][j] for all substrings in O(n^2). Then the palindrome check during backtracking is O(1).
def partition(s): n = len(s) # is_pal[i][j] = True iff s[i:j+1] is a palindrome is_pal = [[False] * n for _ in range(n)] for i in range(n): is_pal[i][i] = True # L1: single chars are palindromes for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length == 2 or is_pal[i + 1][j - 1]): is_pal[i][j] = True # L2: O(1) DP recurrence
result = [] path = []
def backtrack(start): if start == n: result.append(path[:]) # L3: O(n) copy return for end in range(start, n): if is_pal[start][end]: # L4: O(1) table lookup path.append(s[start:end + 1]) # L5: O(k) slice for result backtrack(end + 1) # L6: recurse path.pop()
backtrack(0) return resultWhere the time goes, line by line
Variables: n = len(s).
| Line | Per-call cost | Times executed | Contribution |
|---|---|---|---|
| L1/L2 (DP table build) | O(1) | n^2 cells | O(n^2) |
| L4 (O(1) lookup) | O(1) | O(n · 2^n) | O(n · 2^n) |
| L6 (recurse) | O(1) dispatch | O(2^n) nodes | O(n · 2^n) ← dominates |
The O(n^2) DP preprocessing pays off when there are many palindrome checks; each one drops from O(k) to O(1).
Complexity
- Time: O(n · 2^n). The DP table is O(n^2) once; the backtracking work dominates asymptotically but is constant-factor faster.
- Space: O(n^2) DP + O(n) recursion.
Summary
| Approach | Time | Space |
|---|---|---|
| Backtrack + slice palindrome check | O(n · 2^n) | O(n) |
| Backtrack + two-pointer check | O(n · 2^n) | O(n) |
| Backtrack + precomputed DP | O(n · 2^n) | O(n^2) |
All three have the same dominant term (exponential number of partitions). DP precomputation is the constant-factor win; it’s also how problem 132. Palindrome Partitioning II (min cuts) becomes tractable.
Test cases
def partition(s): n = len(s) is_pal = [[False] * n for _ in range(n)] for i in range(n): is_pal[i][i] = True for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length == 2 or is_pal[i + 1][j - 1]): is_pal[i][j] = True result = []; path = [] def backtrack(start): if start == n: result.append(path[:]); return for end in range(start, n): if is_pal[start][end]: path.append(s[start:end + 1]); backtrack(end + 1); path.pop() backtrack(0) return result
def _run_tests(): r = partition("aab") assert sorted(map(tuple, r)) == sorted([("a","a","b"), ("aa","b")]) assert partition("a") == [["a"]] # all same characters: every prefix is a palindrome r3 = partition("aaa") assert sorted(map(tuple, r3)) == sorted([("a","a","a"), ("a","aa"), ("aa","a"), ("aaa",)]) # single partition only (no internal palindromes) r4 = partition("abc") assert sorted(map(tuple, r4)) == sorted([("a","b","c")]) print("all tests pass")
if __name__ == "__main__": _run_tests()