Palindrome Partition Cost Minimiser
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.