Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Examples
Input: "aab"
Output: 1
Input: "a"
Output: 0
Hints
Use dynamic programming to precompute all possible palindromic substrings in `s` and store them in a 2D array `isPalin[i][j]` where `isPalin[i][j]` is `true` if `s[i..j]` is a palindrome.
Initialize a 1D DP array `dp` where `dp[i]` represents the minimum cuts needed for the substring `s[0..i]`. Set `dp[0] = 0` since a single character is always a palindrome.
For each position `i` in `s`, iterate backward from `i` to `0` to check if `s[j..i]` is a palindrome using the precomputed `isPalin` table. If it is, update `dp[i]` as the minimum of its current value or `dp[j-1] + 1` (if `j > 0`), or `0` if `j == 0`.
Palindrome Partitioning II
Given a string `s`, partition `s` such that every substring of the partition is a palindrome.