Minimize Cuts into Palindromic String Pieces
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Split a nonempty string into contiguous palindromic pieces using the fewest cuts. Return the number of cuts, not the pieces. With `k` pieces there are `k-1` cuts; a string that is already a palindrome needs zero cuts.
```cpp
int minCut(string s);
```
### Examples
```text
Input: s = "abac"
Output: 1
```
The split `aba|c` uses one cut.
```text
Input: s = "abba"
Output: 0
```
### Constraints
- Length is between 1 and 2000.
- Only lowercase English letters occur.
Overview: Minimize palindrome partition cuts using valid substring intervals and optimal prefix piece counts.