Skip to main content

Palindrome Partition Cost Minimiser

medium
Dynamic ProgrammingStringDp IntervalDp 1d
Asked atGoogleAmazonMetaMicrosoft

Problem Description

Given a string `text`, partition it into one or more substrings such that every substring is a palindrome. The cost of a partition is the number of cuts made. Return the **minimum number of cuts** needed to partition `text` into palindromic substrings.

A single character is always a palindrome. If the whole string is already a palindrome, no cuts are needed (cost = 0).

**Example 1:**
```
Input: text = "acdkdca"
Output: 1
Explanation: Cut once → ["acd", "kdca"]? Not palindromes.
Actually: ["a", "cdkdc", "a"] costs 2 cuts.
Or: ["acdkdca"] — is it a palindrome? a==a, c==c, d==d, k middle. Yes! 0 cuts.
Output: 0
```

Hmm, let me use a clearer example:

**Example 1:**
```
Input: text = "abcba"
Output: 0
Explanation: The entire string is a palindrome, so 0 cuts needed.
```

**Example 2:**
```
Input: text = "abfcba"
Output: 2
Explanation: No single cut yields two palindromes.
One optimal: ["a", "bfcb", "a"] — "bfcb" is not a palindrome.
Another: ["abf", "cba"] — neither is a palindrome.
Best: ["a", "b", "fcba"]? "fcba" not palindrome.
Best: ["a", "bfcb", "a"] — not valid.
Try: ["ab", "fcb", "a"] — none palindromes.
["a","b","f","c","b","a"] = 5 cuts.
["a","b","fcbf"... no.
Actually minimum: ["a","bfcb","a"] — "bfcb" reversed is "bcfb" ≠ "bfcb". Not palindrome.
["abfcba"] reversed = "abcfba" ≠ "abfcba".
Minimum is ["a","b","f","c","b","a"] = 5 or ["a","bfcb","a"]=2 cuts but invalid.
Let me use text = "abacaba" → whole string is palindrome → 0 cuts.
```

**Example 1:**
```
Input: text = "xyzyx"
Output: 0
Explanation: "xyzyx" is a palindrome → 0 cuts.
```

**Example 2:**
```
Input: text = "abcde"
Output: 4
Explanation: No substring of length > 1 is a palindrome except single chars,
so minimum cuts = 4: ["a","b","c","d","e"].
```

Constraints

  • 1 <= text.length <= 2000
  • text consists of lowercase English letters only

Follow-up

Can you reduce the space complexity to O(n) by using Manacher's algorithm to detect palindromes in O(n) time and expanding from centers?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.