Introduction

This problem asks for the smallest number of palindromic substrings whose concatenation is the original string. It is a classic dynamic programming problem because many overlapping substrings need to be checked repeatedly. A correct solution is much more efficient than trying every possible partition.

Problem Description

Given a string s, split it into contiguous pieces so that every piece is a palindrome and the number of pieces is minimized.

Examples:

• abacaba needs only 1 part because the whole string is a palindrome.
• banana can be split as b | anana, so the minimum number of parts is 2.

If you are solving the related "minimum cuts" variant, the answer is simply:

minimum parts - 1

Dynamic Programming Idea

There are two subproblems:

1. Determine whether s[start:end+1] is a palindrome.
2. Compute the minimum number of palindromic parts needed for each prefix of the string.

Define:

• is_pal[start][end] as True if the substring is a palindrome
• parts[end] as the minimum number of palindromic parts needed for s[0:end+1]

For each end, try every start <= end. If s[start:end+1] is a palindrome, then:

• if start == 0, the candidate answer is 1
• otherwise the candidate answer is parts[start - 1] + 1

Take the minimum over all such candidates.

Why This Works

If a partition ends with a palindromic suffix, then the part before that suffix must itself be an optimal solution for the prefix. That is exactly the structure dynamic programming needs:

• optimal substructure
• overlapping subproblems

Without memoization or DP, a brute-force search over all partitions becomes exponential.

Python Implementation

1def min_palindrome_partition(s: str) -> tuple[int, list[str]]:
2    n = len(s)
3    if n == 0:
4        return 0, []
5
6    is_pal = [[False] * n for _ in range(n)]
7    parts = [float("inf")] * n
8    prev_start = [-1] * n
9
10    for end in range(n):
11        for start in range(end, -1, -1):
12            if s[start] == s[end] and (end - start < 2 or is_pal[start + 1][end - 1]):
13                is_pal[start][end] = True
14
15                candidate = 1 if start == 0 else parts[start - 1] + 1
16                if candidate < parts[end]:
17                    parts[end] = candidate
18                    prev_start[end] = start
19
20    pieces = []
21    end = n - 1
22    while end >= 0:
23        start = prev_start[end]
24        pieces.append(s[start:end + 1])
25        end = start - 1
26
27    pieces.reverse()
28    return parts[-1], pieces
29
30
31count, partition = min_palindrome_partition("banana")
32print(count)       # 2
33print(partition)   # ['b', 'anana']

This implementation computes both the minimum number of parts and one optimal partition.

Complexity

The standard DP solution runs in O(n^2) time:

• there are O(n^2) substrings
• each start, end pair is processed once

The straightforward version uses O(n^2) space because of the palindrome table.

Worked Example

Consider banana.

Important palindromic substrings include:

• b
• a
• n
• ana
• anana

The best partition is:

b | anana

So:

• minimum parts = 2
• minimum cuts = 1

That is much better than naive partitions like b | ana | n | a.

Common Pitfalls

• Confusing "minimum parts" with "minimum cuts".
• Forgetting that a whole string can itself be a palindrome.
• Rechecking palindromes from scratch inside the DP loop, which can accidentally turn the solution into O(n^3).
• Using the wrong example result for banana. The optimal answer is 2 parts, not 4.

Summary Table