Common Patterns - Learning Module

Loading content...

0/276

Palindrome Partitioning

Dissecting Strings into Symmetry

Consider the string "aab". How many ways can you split it so that every piece reads the same forwards and backwards? The answer might surprise you: there are two ways—["a","a","b"] and ["aa","b"]. Each partition consists entirely of palindromes.

The Palindrome Partitioning problem combines string processing with backtracking in an elegant dance. It asks us to find all ways to partition a string such that every resulting substring is a palindrome. This problem appears in text processing, data compression, and even DNA sequence analysis, where finding symmetric patterns within sequences has biological significance.

What makes this problem fascinating is how it transforms a seemingly linear string operation into a tree exploration problem. At each position, we face choices: where should the next cut be? The backtracking framework lets us systematically explore every possibility.

What You Will Learn

By the end of this page, you will understand the Palindrome Partitioning problem completely, implement both naive and optimized solutions using dynamic programming for palindrome checking, analyze the time and space complexity, and recognize how this pattern applies to other string partitioning problems.

Formal Problem Statement

The Palindrome Partitioning Problem (LeetCode 131):

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Definitions:

A partition of a string is a way of splitting it into one or more non-empty substrings that concatenate to form the original string.
A palindrome is a string that reads the same forward and backward (e.g., "aba", "aa", "a").

Example 1:

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

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 ≤ s.length ≤ 16
s contains only lowercase English letters

The small constraint on string length (≤ 16) hints that an exponential algorithm is acceptable—there can be up to 2^(n-1) partitions of a string of length n.

Understanding PartitionsConsider s = "aab" to understand what valid partitions look like:

Input

s = "aab"

Output

[["a","a","b"], ["aa","b"]]

Explanation

Partition ["a","a","b"]: three cuts resulting in single-character substrings (all single chars are palindromes). Partition ["aa","b"]: "aa" is a palindrome, "b" is a palindrome. Invalid partition ["aab"]: the entire string "aab" is NOT a palindrome, so this doesn't count. Invalid partition ["a","ab"]: "ab" is not a palindrome.

The Partition Structure

A partition is defined by where we make cuts in the string. For a string of length n, there are n-1 possible cut positions (between each pair of adjacent characters). Each cut position is either used or not, giving 2^(n-1) possible partitions. Our job is to filter those where every piece is a palindrome.

The Backtracking Approach

The Palindrome Partitioning problem naturally maps to backtracking because we're exploring a decision tree where each node represents a choice.

The Decision at Each Position:

Imagine we're at position i in the string. We need to decide: where does the current palindrome end? We could take:

Just s[i] (length 1) as the next palindrome, then continue from i+1
s[i:i+2] (length 2) if it's a palindrome, then continue from i+2
s[i:i+3] (length 3) if it's a palindrome, then continue from i+3
...and so on until the end of the string

This creates a tree:

For s = "aab":

Start at index 0
├── Take "a" (palindrome ✓), continue from 1
│   ├── Take "a" (palindrome ✓), continue from 2
│   │   └── Take "b" (palindrome ✓), continue from 3 → DONE: ["a","a","b"]
│   └── Take "ab" (palindrome ✗) → Prune
└── Take "aa" (palindrome ✓), continue from 2
    └── Take "b" (palindrome ✓), continue from 3 → DONE: ["aa","b"]
└── Take "aab" (palindrome ✗) → Prune

The Pruning Condition:

We prune a branch whenever the current substring is not a palindrome. This avoids exploring subtrees that can never lead to valid partitions. The earlier we detect non-palindromes, the more computation we save.

Mapping to the Backtracking Template

•State: Current position index in the string, and the current partition path built so far.
•isComplete: We've reached the end of the string (index == len(s)), meaning we've successfully partitioned the entire string.
•getChoices: All substrings starting at index: s[index:index+1], s[index:index+2], ..., s[index:n].
•isValid: The chosen substring is a palindrome.
•make(choice): Add the palindrome substring to the current path.
•undo(choice): Remove the last substring from the path (pop).

Implementing the Basic Solution

Let's implement the straightforward backtracking solution with an inline palindrome check.

palindrome_partition_basic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def partition(s: str) -> list[list[str]]:
    """
    Find all palindrome partitions of string s.
    
    Basic approach: backtracking with inline palindrome check.
    
    Time Complexity: O(n * 2^n) where n = len(s)
    Space Complexity: O(n) for recursion depth and current path
    """
    result = []
    
    def is_palindrome(substring: str) -> bool:
        """Check if a string is a palindrome."""
        return substring == substring[::-1]
    
    def backtrack(index: int, path: list[str]) -> None:
        # Base case: reached end of string, valid partition found
        if index == len(s):
            result.append(path[:])  # Append a copy
            return
        
        # Try all possible substrings starting at 'index'
        for end in range(index + 1, len(s) + 1):
            substring = s[index:end]
            
            # Only proceed if the substring is a palindrome
            if is_palindrome(substring):
                # CHOOSE: Add this palindrome to our partition
                path.append(substring)
                
                # EXPLORE: Continue partitioning the rest of the string
                backtrack(end, path)
                
                # UNCHOOSE: Remove the palindrome (backtrack)
                path.pop()
    
    backtrack(0, [])
    return result
 
 
# Example usage
print(partition("aab"))
# Output: [['a', 'a', 'b'], ['aa', 'b']]
 
print(partition("aaba"))
# Output: [['a', 'a', 'b', 'a'], ['a', 'aba'], ['aa', 'b', 'a']]
 
print(partition("aaaa"))
# Output: Many partitions including ['aaaa'], ['aa', 'aa'], ['a', 'a', 'a', 'a'], etc.

The End Index Convention

We iterate 'end' from index+1 to len(s)+1 because Python/TypeScript slicing s[index:end] excludes the end index. So s[0:1] gives us s[0], s[0:2] gives us s[0:1], etc. This is a common source of off-by-one errors—always trace through with a small example!

Optimizing with Dynamic Programming

The basic solution rechecks palindrome status for overlapping substrings. For example, when exploring different paths, we might check if "aba" is a palindrome multiple times.

The Redundancy Problem:

Consider s = "ababa". During backtracking:

Path 1: Check "a", then "bab", then "a"
Path 2: Check "aba", then "ba"
Path 3: Check "a", then "b", then "aba"

The substring "aba" is checked multiple times across different paths. For longer strings, this redundancy becomes significant.

The DP Solution:

We precompute a 2D table is_palindrome[i][j] that tells us whether s[i:j+1] is a palindrome. The recurrence:

is_palindrome[i][j] = (s[i] == s[j]) AND is_palindrome[i+1][j-1]

Base cases:

Single characters: is_palindrome[i][i] = True
Two characters: is_palindrome[i][i+1] = (s[i] == s[i+1])

We fill the table by increasing substring length, ensuring that when we compute is_palindrome[i][j], we've already computed is_palindrome[i+1][j-1].

palindrome_partition_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def partition_optimized(s: str) -> list[list[str]]:
    """
    Find all palindrome partitions with DP-precomputed palindrome checking.
    
    Optimization: Precompute is_palindrome[i][j] for all substrings.
    
    Time Complexity: O(n^2) for precomputation + O(n * 2^n) for backtracking
    Space Complexity: O(n^2) for the DP table + O(n) for recursion
    """
    n = len(s)
    
    # Step 1: Precompute palindrome table
    # is_pal[i][j] = True if s[i:j+1] is a palindrome
    is_pal = [[False] * n for _ in range(n)]
    
    # All single characters are palindromes
    for i in range(n):
        is_pal[i][i] = True
    
    # Check two-character substrings
    for i in range(n - 1):
        is_pal[i][i + 1] = (s[i] == s[i + 1])
    
    # Fill for lengths 3 and above
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # s[i:j+1] is palindrome if s[i]==s[j] and inner part is palindrome
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i + 1][j - 1]
    
    # Step 2: Backtracking with O(1) palindrome lookup
    result = []
    
    def backtrack(index: int, path: list[str]) -> None:
        if index == n:
            result.append(path[:])
            return
        
        for end in range(index, n):
            # O(1) palindrome check using precomputed table
            if is_pal[index][end]:
                path.append(s[index:end + 1])
                backtrack(end + 1, path)
                path.pop()
    
    backtrack(0, [])
    return result
 
 
# Example with timing comparison
import time
 
s = "aaaaaaaaaaaaa"  # 13 a's - many palindrome partitions
 
start = time.time()
result_basic = partition(s)  # Basic version
basic_time = time.time() - start
 
start = time.time()
result_optimized = partition_optimized(s)
optimized_time = time.time() - start
 
print(f"Basic: {len(result_basic)} partitions in {basic_time:.4f}s")
print(f"Optimized: {len(result_optimized)} partitions in {optimized_time:.4f}s")
# Optimized version is noticeably faster for repeated palindrome checks

Index Convention Difference

Notice the subtle index change in the optimized version: we iterate 'end' from index to n-1 (inclusive), and use s[index:end+1] for the substring. The DP table uses inclusive indices is_pal[i][j] for s[i..j], matching how we typically think about substrings mathematically. Be careful to stay consistent!

Complexity Analysis

Let's rigorously analyze both the basic and optimized solutions.

Basic Solution Complexity:

Time Complexity: O(n × 2^n)

There are O(2^(n-1)) possible partitions (each of n-1 cut positions is used or not)
For each partition, we check palindrome status for each piece
Palindrome checking for a piece of length k takes O(k)
Total work per partition sums to O(n) across all pieces
Overall: O(n × 2^n)

Space Complexity: O(n)

Recursion depth is at most n (partition into all single characters)
Current path stores at most n substrings
Result storage is not counted (output-dependent)

Optimized Solution Complexity:

Time Complexity: O(n^2) + O(n × 2^n) = O(n × 2^n)

Precomputation: O(n^2) to fill the DP table
Backtracking: O(2^n) partitions × O(n) work per partition
The O(n^2) precomputation is dominated by O(n × 2^n)
However, in practice, the constant factors are much smaller because each palindrome check is O(1) vs O(n)

Space Complexity: O(n^2)

The is_palindrome table requires O(n^2) space
Plus O(n) for recursion stack

Complexity Comparison
Aspect	Basic Solution	Optimized Solution
Time – Precomputation	O(1)	O(n²)
Time – Per palindrome check	O(n)	O(1)
Time – Total	O(n × 2ⁿ)	O(n × 2ⁿ) but faster constants
Space – Auxiliary	O(n)	O(n²)
Best for	Small n or few palindromes	Large n or many repeated checks

When to Optimize

The DP precomputation shines when the same substring is checked multiple times. For strings like "aaaa...a" where almost every substring is a palindrome, optimization provides substantial speedup. For strings with few palindromes (like "abcdefghij"), most branches are pruned early, and the basic solution may suffice.

Variations and Related Problems

The Palindrome Partitioning pattern extends to several related problems that test your understanding more deeply.

Palindrome Partitioning II (LeetCode 132):

Instead of finding all partitions, find the minimum number of cuts needed to partition the string into palindromes.

This transforms from backtracking to pure DP:

dp[i] = minimum cuts needed for s[0:i+1]
For each j ≤ i, if s[j:i+1] is a palindrome: dp[i] = min(dp[i], dp[j-1] + 1)

Palindrome Partitioning III (LeetCode 1278):

Partition the string into exactly k non-empty substrings and make each substring a palindrome by changing at most some characters. Find the minimum changes needed.

This requires tracking two dimensions: position and number of partitions.

Palindrome Partitioning IV (LeetCode 1745):

Can the string be partitioned into exactly three non-empty palindromic substrings?

This can be solved in O(n²) by precomputing palindrome status and checking all possible split points.