Scale Engineer

Palindrome Partitioning II

Hard
#0132Time: O(n^3)Space: O(n)
Patterns
Dynamic Programming
Data structures
String

Prompt

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.

 

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion with memoization to find the minimum cuts. It explores all possible partitions starting from the beginning of the string. For each potential first palindrome substring, it recursively finds the minimum cuts for the rest of the string. Memoization is used to store the results for subproblems (minimum cuts for suffixes of the string) to avoid redundant calculations. However, the palindrome check for each substring is done naively, leading to a cubic time complexity.

Algorithm

  • The core idea is to use recursion to solve the problem for sub-strings.
  • Define a recursive function, say findMinCut(start), which calculates the minimum cuts needed for the suffix of the string starting at start.
  • The base case for the recursion is when start reaches the end of the string. In this case, no more cuts are needed. We return -1 to correctly handle the 1 + recursive_call logic (a single partition has 0 cuts).
  • For a given start index, iterate through all possible end points i from start to n-1.
  • For each i, check if the substring s[start...i] is a palindrome.
  • If it is a palindrome, we can make a cut after this substring. The total cuts for this choice would be 1 + findMinCut(i + 1).
  • Keep track of the minimum cuts found among all valid palindrome partitions.
  • To avoid recomputing results for the same subproblems (i.e., the same start index), use a memoization array memo to store the results.

Walkthrough

We can define a function findMinCut(start) that computes the minimum cuts for the substring s[start...n-1]. To find findMinCut(start), we can iterate from i = start to n-1. If the substring s[start...i] is a palindrome, we've found a valid partition. We can then make a cut after i and recursively find the minimum cuts for the remaining part of the string, s[i+1...n-1], which is findMinCut(i+1). The total cuts for this choice would be 1 + findMinCut(i+1). We take the minimum over all possible choices of i.

This recursive structure has overlapping subproblems, as findMinCut for a particular index might be called multiple times. We can optimize this using a memoization array, memo, where memo[start] stores the result of findMinCut(start).

The palindrome check itself is done in a helper function that takes O(L) time, where L is the length of the substring. Since this check is inside the recursive function's loop, the overall complexity becomes O(n^3).

class Solution {    private Integer[] memo;    private String s;     public int minCut(String s) {        this.s = s;        this.memo = new Integer[s.length()];        return solve(0);    }     private int solve(int start) {        if (start >= s.length() - 1 || isPalindrome(start, s.length() - 1)) {            return 0;        }        if (memo[start] != null) {            return memo[start];        }         int minCuts = s.length() - 1 - start; // Max possible cuts        for (int i = start; i < s.length(); i++) {            if (isPalindrome(start, i)) {                minCuts = Math.min(minCuts, 1 + solve(i + 1));            }        }        return memo[start] = minCuts;    }     private boolean isPalindrome(int low, int high) {        while (low < high) {            if (s.charAt(low++) != s.charAt(high--)) {                return false;            }        }        return true;    }}

Complexity

Time

O(n^3)

Space

O(n)

Trade-offs

Pros

  • Conceptually simpler than iterative dynamic programming.

  • Memoization helps avoid the exponential complexity of a pure brute-force recursion.

Cons

  • The time complexity is high due to the repeated palindrome checks within the recursion.

  • For each state, it iterates and calls a palindrome checking function, leading to an overall cubic time complexity.

  • This approach will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for a problem of this scale.

Solutions

using System ; using System.Collections.Generic ; public class Solution { public int MinCut ( string s ) { if ( s . Length == 0 ) return 0 ; var paths = new List < int >[ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { int j , k ; for ( j = i , k = i + 1 ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } for ( j = i , k = i ; j >= 0 && k < s . Length ; -- j , ++ k ) { if ( s [ j ] == s [ k ]) { if ( paths [ k ] == null ) { paths [ k ] = new List < int >(); } paths [ k ]. Add ( j - 1 ); } else { break ; } } } var partCount = new int [ s . Length ]; for ( var i = 0 ; i < s . Length ; ++ i ) { partCount [ i ] = int . MaxValue ; if ( paths [ i ] != null ) { foreach ( var path in paths [ i ]) { if ( path < 0 ) { partCount [ i ] = 0 ; break ; } else { partCount [ i ] = Math . Min ( partCount [ i ], partCount [ path ]); } } } ++ partCount [ i ]; } return partCount [ s . Length - 1 ] - 1 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem