332. Palindrome Partitioning Problem (Minimum Cuts)

Given a string, find the minimum number of cuts needed to partition it into pieces such that every piece is itself a palindrome. A string that's already a palindrome needs 0 cuts.

Input: A single line contains the string s. Output: Print a single integer - the minimum number of cuts to partition s into all-palindrome pieces.

1 <= |s| <= 1000

This problem builds directly on 'Count Palindromic Partitions' and 'Print All Palindromic Partitions' from the Backtracking category - all three share the same palindrome-checking foundation, just asking for a count, a minimum, or an exhaustive list respectively.

Find the minimum number of cuts needed to split a string into pieces that are all palindromes. Brute force: Try every possible way of inserting cut points and check if every resulting piece is a palindrome, tracking the minimum cuts - this is exponential (2^(n-1) possible cut patterns), impractical for |s| up to 1000. Optimised: Precomputing the palindrome-check table ONCE (O(n²)) turns every 'is this substring a palindrome' check during the cut-minimization DP into an O(1) lookup - combined with the dp[i] recurrence (trying every possible LAST piece ending at i), this avoids ever re-verifying the same substring's palindrome status repeatedly.

First build a 2D table isPal[i][j] with its own O(n^2) DP, where isPal[i][j] is true exactly when s[i] equals s[j] and isPal[i+1][j-1] is true, so afterward any 'is s[i..j] a palindrome' question is an O(1) lookup. Then compute the same cuts[i] DP as before, but every inner check is now O(1) instead of O(n), which collapses the overall time complexity. Time: O(n^2) Space: O(n^2)

Define cuts[i] as the minimum cuts needed for the prefix s[0..i]. For each i, try every j at or before i as a potential start of the last piece, check directly (scanning inward from both ends) whether s[j..i] is a palindrome, and if so update cuts[i] to the smaller of its current value and cuts[j-1] + 1. This turns the problem into a clean O(n^2) DP recurrence, but each palindrome check inside it still costs up to O(n), so no palindrome information is reused across DP states yet. Time: O(n^3) Space: O(n)

Recursively try every way to cut the string into pieces, at each position either cutting or not, and for every complete partition produced, check whether every piece is a palindrome by scanning it from both ends; track the minimum number of cuts among the all-palindrome partitions found. This explores the full exponential space of ways to slice the string. Time: O(2^n * n) Space: O(n)

1. First precompute isPal[i][j] = whether s[i..j] is a palindrome, filled by increasing substring length. 2. dp[i] = minimum cuts needed for the prefix s[0..i]; if isPal[0][i] is true, dp[i]=0 (the whole prefix is already a palindrome, no cuts needed). 3. Otherwise, dp[i] = min over every k<i where isPal[k+1][i] is true, of dp[k]+1 - cutting right after position k, making s[k+1..i] the last (palindromic) piece.

Time: O(n²) - both the palindrome precomputation and the cut-minimization DP are O(n²). Space: O(n²), for the palindrome table (the dp array itself is only O(n)).

Test s that is already a palindrome (0 cuts), a single-character s (0 cuts), and |s| = 1000 (upper bound) for the O(n^2) DP's performance.

Be ready to explain WHY precomputing the palindrome table first is essential for efficiency - without it, checking 'is s[k+1..i] a palindrome' from scratch inside the cut-minimization loop would cost an ADDITIONAL O(n) each time, making the overall algorithm O(n³) instead of O(n²).