Palindrome Partitioning

Difficulty: Medium Source: NeetCode

Problem

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

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

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

Constraints:

• 1 <= s.length <= 16
• s consists only of lowercase English letters.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Palindrome checking — a string equals its reverse; or check with two pointers
• Backtracking — at each position, try all possible next substrings
• Subsets/combinations — this problem is about choosing “cut points” in the string

1. Brute Force

Intuition

At each index in the string, try every possible prefix ending at some index end. If the prefix is a palindrome, add it to the current partition and recurse on the remainder of the string. When the start index reaches the end of the string, we’ve partitioned the whole string into palindromes — record it. This is already basically the optimal backtracking approach; there’s no fundamentally simpler way to enumerate all partitions.

Algorithm

1. Define backtrack(start, current).
2. If start == len(s): append a copy of current to results and return.
3. For end from start + 1 to len(s):
   • Extract substr = s[start:end].
   • If substr is a palindrome:
     • Append substr to current.
     • Recurse with start = end.
     • Pop substr.

Solution

def partition_brute(s):
    result = []

    def is_palindrome(sub):
        return sub == sub[::-1]

    def backtrack(start, current):
        if start == len(s):
            result.append(list(current))
            return
        for end in range(start + 1, len(s) + 1):
            substr = s[start:end]
            if is_palindrome(substr):
                current.append(substr)
                backtrack(end, current)
                current.pop()

    backtrack(0, [])
    return result


print(partition_brute("aab"))  # [['a', 'a', 'b'], ['aa', 'b']]
print(partition_brute("a"))    # [['a']]

Complexity

• Time: O(n * 2^n) — up to 2^(n-1) partitions, each palindrome check takes O(n)
• Space: O(n) — recursion depth

2. Backtracking with DP Palindrome Precomputation

Intuition

The approach is the same as brute force, but we precompute a 2D table dp[i][j] that stores whether s[i:j+1] is a palindrome. This turns every palindrome check from O(n) into O(1), which helps when the string is longer. dp[i][j] is a palindrome if s[i] == s[j] and either the substring is length 1 or 2, or dp[i+1][j-1] is also a palindrome.

Algorithm

1. Precompute dp[i][j] = True if s[i:j+1] is a palindrome.
2. Run the same backtracking, but use dp[start][end-1] instead of calling is_palindrome.

Solution

def partition(s):
    n = len(s)
    # precompute palindrome table
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
                dp[i][j] = True

    result = []

    def backtrack(start, current):
        if start == n:
            result.append(list(current))
            return
        for end in range(start, n):
            if dp[start][end]:  # O(1) palindrome check
                current.append(s[start:end + 1])
                backtrack(end + 1, current)
                current.pop()

    backtrack(0, [])
    return result


print(partition("aab"))       # [['a', 'a', 'b'], ['aa', 'b']]
print(partition("a"))         # [['a']]
print(partition("aba"))       # [['a', 'b', 'a'], ['aba']]
print(partition("aabaa"))     # multiple valid partitions

Complexity

• Time: O(n^2) for DP precomputation + O(n * 2^n) for backtracking — overall O(n * 2^n)
• Space: O(n^2) for the DP table + O(n) recursion depth

Common Pitfalls

Off-by-one in the end range. The substring s[start:end] uses Python’s exclusive upper bound. If you want to include s[end], you need s[start:end+1]. When using the DP table, dp[start][end] checks if s[start..end] (inclusive) is a palindrome, so you pass the end index inclusively.

Appending current without copying. Always result.append(list(current)). If you append the reference, all stored partitions will point to the same list and end up empty after the recursion finishes.

Forgetting to try single-character substrings. Every single character is trivially a palindrome. Make sure your loop starts at end = start (for the DP version) or end = start + 1 (for the slice version where s[start:start+1] is one character). A common mistake is starting at end = start + 2, which would skip single characters.