Introduction

For palindrome partitioning, time complexity depends heavily on what the algorithm is actually producing. If it generates all valid partitions, the output itself can already be exponential, so no implementation can avoid that worst-case growth. A correct analysis has to separate the cost of exploring partitions, checking palindromes, and materializing the result.

Clarify the Problem Variant First

“Palindrome partitioning” usually refers to one of these tasks:

• generate all palindrome partitions
• compute the minimum number of cuts
• count how many valid partitions exist

These are different problems with different complexities.

This article focuses on the common backtracking version that returns all valid palindrome partitions of a string.

Naive Backtracking Structure

A standard recursive algorithm tries every possible cut position and checks whether the current prefix is a palindrome.

1def is_palindrome(s: str) -> bool:
2    return s == s[::-1]
3
4def partitions(s: str):
5    result = []
6
7    def dfs(start: int, path: list[str]):
8        if start == len(s):
9            result.append(path[:])
10            return
11
12        for end in range(start + 1, len(s) + 1):
13            piece = s[start:end]
14            if is_palindrome(piece):
15                path.append(piece)
16                dfs(end, path)
17                path.pop()
18
19    dfs(0, [])
20    return result
21
22print(partitions("aab"))

This is easy to understand, but its worst-case behavior is expensive.

Why the Number of Partitions Is Exponential

In the worst case, such as a string of identical characters like "aaaaa", every substring is a palindrome. That means every place between characters can either contain a cut or not contain a cut.

For a string of length n, there are n - 1 possible cut positions, so the number of possible partitions is:

2^(n - 1)

That already gives an exponential lower bound for any algorithm that must output all partitions.

So even before counting palindrome checks, the output size is exponential.

Cost of Palindrome Checking in the Naive Version

In the naive algorithm above, each candidate substring is tested with a palindrome check that can take O(n) time in the worst case.

That means the full runtime is often described as:

O(n^2 * 2^n)

Why that form is reasonable:

• there are exponentially many recursive paths in the worst case
• many candidate substrings are checked
• each palindrome check may cost linear time

This is a better worst-case bound than the too-optimistic O(n * 2^n) claim for the naive version.

Improve Palindrome Checks with Dynamic Programming

You can precompute whether every substring is a palindrome in O(n^2) time, then use that table during backtracking.

1def palindrome_table(s: str):
2    n = len(s)
3    dp = [[False] * n for _ in range(n)]
4
5    for i in range(n - 1, -1, -1):
6        for j in range(i, n):
7            if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
8                dp[i][j] = True
9
10    return dp

Then the backtracking step can test palindromes in O(1):

1def partitions_fast(s: str):
2    n = len(s)
3    dp = palindrome_table(s)
4    result = []
5
6    def dfs(start: int, path: list[str]):
7        if start == n:
8            result.append(path[:])
9            return
10
11        for end in range(start, n):
12            if dp[start][end]:
13                path.append(s[start:end + 1])
14                dfs(end + 1, path)
15                path.pop()
16
17    dfs(0, [])
18    return result

Complexity of the Optimized Version

With precomputed palindrome lookup:

• DP build cost is O(n^2)
• backtracking still explores exponentially many valid partitions in the worst case
• output construction still costs at least linear work per emitted partition

So the optimized all-partitions version is commonly described as:

O(n^2 + n * 2^n)

The exponential term is still unavoidable because the output itself can be exponential.

Space Complexity

For the naive backtracking version:

• recursion depth can be O(n)
• stored output can be exponential in the worst case

For the DP-enhanced version:

• palindrome table costs O(n^2)
• recursion still costs O(n)
• result storage is still exponential

If the algorithm returns all partitions, result storage is usually the dominant cost.

Common Analysis Mistakes

A frequent mistake is ignoring output size and claiming a polynomial runtime for a function that returns all partitions.

Another mistake is counting only the recursive branching and forgetting the cost of substring palindrome checks in the naive version.

A third mistake is mixing the “minimum cuts” problem with the “enumerate all partitions” problem and reusing the wrong complexity result.

Common Pitfalls

One common pitfall is saying the backtracking algorithm is just O(2^n) without mentioning palindrome-check cost or output materialization.

Another issue is assuming DP makes the entire problem polynomial. It only removes repeated palindrome checking; it does not eliminate exponential output growth.

A third mistake is using the same complexity statement for both naive and DP-assisted solutions.

Summary

• If the algorithm returns all palindrome partitions, worst-case output size is already exponential.
• Naive backtracking with direct palindrome checks is typically O(n^2 * 2^n) in the worst case.
• Precomputing palindrome status reduces that to about O(n^2 + n * 2^n).
• The exponential term remains because the number of valid partitions can be 2^(n - 1).
• Always identify which palindrome-partitioning variant you are analyzing before stating complexity.