Problem Statement

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.

LeetCode:

• https://leetcode.com/problems/palindrome-partitioning-ii/description/

Examples

Example 1:

Input: s = "aab"
Output: 1

Explanation: The palindrome partitioning ["aa", "b"] could be produced using 1 cut.

Example 2:

Input: s = "abaaba"
Output: 0

Explanation: The complete string can be considered as a partition as the string itself is palindrome.
There are other ways to partition the string but it requires more number of cuts.

Different Approaches

1️⃣ Recursive Approach)

Understanding:

In order to solve this problem, we need to partition the given string in such a way that every substring of the partition becomes a palindrome. For example, if the string “aabb” is given, one of the valid partitions will be “aa | b | b”.

Now, one key point to notice here is that we can make every substring of any string a palindrome, by partitioning it n-1 times(where n = size of the string). For example, if the given string is “abcd” and if we partition it n-1 i.e. (4-1 = 3) times, it will be like, a | b | c | d. Here, every single substring of the partitions is a palindrome.

So, we can conclude that it is very much possible all the time to partition a string in such a way that every substring becomes a palindrome and we can also assure that the answer always exists. Here, in this question, it is clearly mentioned that we need to figure out the minimum number of such partitions. Consider the example given below:

Intuition:

This type of problem is generally solved using the front partition. Following the front partition technique, we will start checking from the first index of the given string and will check if we can make a partition between the first and the second index. Similarly, then we will include the second index in the account and check if we can make a partition between the second and the third index. This process will continue to the last index. The condition for a partition to be valid is that the left part of the partition must be a palindromic substring.

Rules to solve this problem:

• Express the given string in terms of the index: We are given a string. Now, following the front partition rules we will place i to index 0 i.e. the first index.

• Try out all partitions: As we have figured out the logic for marking the pointer, i, we will move to the partitioning loop. We can simply write a for loop(say j) starting from i to n-1 (n = size of the string), The problem is being broken in the following manner:

  

  /*It is a pseudocode and it not tied to
  any specific programming language*/
  
  f(i){
      //Partition loop
      for(int j = i; j < n; j++){
          //Calculation
      }
  }

• Base case: When the index i will be equal to the size of the string(i.e. i == n), we can say there are no more characters left to be partitioned. So, this is the base case and in this case, the function will return 0.

• Return the best possible answer of all partitions: A partition is possible when the left substring of that partition is a palindrome. Now, inside the partitioning loop, we will check if the partition can be done at index j(i.e. We will check if the substring starts from index i and ends at index j is a palindrome or not). If it is done, we will add 1 to our answer, and then we will again follow the same method for the left-over substring.
  Here, in the question, it is clearly mentioned that we need the minimum number of partitions. So, calculating all possible answers using the above method, we will take the minimum into our consideration.

  /*It is a pseudocode and it not tied to
  any specific programming language*/
  
  f(i){
      //Partition loop
      for(int j = i; j < n; j++){
          if(isPalindrome(s, i, j)){
              int cost = 1 + f(j+1, s)
              minCost = min(minCost, cost)
          }
      }
      return minCost
  }

Not about the final answer:

If we carefully observe, we can notice that our function is actually counting an extra partition at the end of the string in each case. For example, the given string is “abcd”. After doing a partition after ‘c’ the function will check if a partition can be done after ‘d’ to check if the last substring i.e. ‘d’ itself is a palindrome. Consider the following illustration:

For that our function will return 4 as the answer, instead of the actual answer is 3. So, our actual answer will be (number of partitions returned by the function - 1).

Steps for recursive approach:

1. Convert the problem to a recursive function marked by the pointer i.
2. Use a loop to check all possible partitions of the string and calculate the number of partitions.
3. Return the minimum number of partitions counted.
4. Base case: When the index i will be equal to the size of the string(i.e. i == n), we can say there are no more characters left to be partitioned. So, this is the base case and in this case, the function will return 0.

Code:

class Solution {
public:
    // ✅ Helper function to check if substring s[i..j] is a palindrome
    bool isPalindrome(string& s, int i, int j) {
        while (i < j) {
            if (s[i] == s[j]) {
                i++;
                j--;
            } else {
                return false; // Not a palindrome
            }
        }
        return true; // It is a palindrome
    }

    // ✅ Recursive function to find minimum number of palindromic partitions starting from index i
    int solve(string& s, int i) {
        // Base case: If we've reached the end of the string, no more cuts needed
        if (i == s.size()) {
            return 0;
        }
        
        int minCuts = INT_MAX;

        // Try all possible end positions j for a partition starting from i
        for (int j = i; j < s.size(); j++) {
            
            // If s[i..j] is a palindrome, we can cut here
            if (isPalindrome(s, i, j)) {
                // 1 cut for s[i..j], then recursively solve the rest s[j+1..end]
                int currCuts = 1 + solve(s, j + 1);

                // Take the minimum over all such valid partitions
                minCuts = min(minCuts, currCuts);
            }
        }

        return minCuts;
    }

    // ✅ Main function to return the minimum number of cuts needed
    int minCut(string s) {
        // We subtract 1 because solve() counts the number of palindromic partitions
        // But number of cuts = number of partitions - 1
        return solve(s, 0) - 1;
    }
};

Complexity Analysis:

• Time Complexity:O(n * 2^n)
  • We are trying all possible partitions.
  • At each index i, we are try up to n-1 substrings.
  • At each character, we either cut or don't → binary decisions → 2^n states
  • Each check for isPalindrome() can take up to O(n} time (because of while loop).
• Space Complexity:O(n)
  • Call stack depth.

2️⃣ Memoization

Code:

class Solution {
public:
    // ✅ Helper function to check if s[i..j] is a palindrome
    bool isPalindrome(string& s, int i, int j) {
        while (i < j) {
            if (s[i] == s[j]) {
                i++;
                j--;
            } else {
                return false;  // Mismatch found → not a palindrome
            }
        }
        return true;  // All characters matched → palindrome
    }

    // ✅ Recursive function to return min number of palindromic partitions from index i to end
    int solve(string& s, int i, vector<int>& dp) {
        // 🔚 Base case: if we've reached end of string, no cuts needed
        if (i == s.size()) {
            return 0;
        }

        // ⚡ Return already computed result (memoization)
        if (dp[i] != -1) {
            return dp[i];
        }
        
        int minCuts = INT_MAX;

        // 🧪 Try all possible partitions: s[i..j] for j = i to n-1
        for (int j = i; j < s.size(); j++) {
            // ✅ If s[i..j] is a palindrome
            if (isPalindrome(s, i, j)) {
                // ✂️ 1 cut after s[i..j], then solve for remaining s[j+1..end]
                int currCuts = 1 + solve(s, j + 1, dp);

                // 🧮 Track the minimum over all valid partitions
                minCuts = min(minCuts, currCuts);
            }
        }

        // 🗂️ Save result in dp and return
        return dp[i] = minCuts;
    }

    // ✅ Main function: returns the minimum number of cuts needed to partition string
    int minCut(string s) {
        // 🛠️ Initialize DP array to store results for each index i
        vector<int> dp(s.size(), -1);

        // 📉 Subtract 1 because number of cuts = number of parts - 1
        return solve(s, 0, dp) - 1;
    }
};

Complexity Analysis:

• Time Complexity:O(n^3)
  • There are n states due to memoization
  • Each solve(i) call
    • You loop j from i to n-1 → O(n) choices
    • For each (i, j), you call isPalindrome(s, i, j), which takes O(n) time in the worst case.

  • Total time:

    T(n) = O(n) [states] × O(n) [j loop] × O(n) [palindrome check]
         = O(n³)
    

• Space Complexity:O(n + n)
  • O(n) for the dp array
  • O(n) for the recursive stack depth

3️⃣ Tabulation

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

1. Declare a dp array of size [n+1]: Here, as we need to check dp[j+1] every time, the function will give a runtime error if j = n-1. To avoid this, we will take the array size as n+1 instead of n.
2. Handle the base case: We knew in the recursive code the base case was when i == n, it meant that there were no characters left, we were returning 0. So, to cover this case we can initialize the entire dp array with 0.
3. Next, memoization is a top-down approach, whereas tabulation is bottom-up. Our changing parameter i will change in opposite directions, i.e i will change from n-1→0.
4. After that, copy down the recursive logic inside the nested loops to get the tabulation code.

Code:

class Solution {
public:
    // Helper function to check if a substring s[i..j] is a palindrome
    bool isPalindrome(string& s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    int minCut(string s) {
        int size = s.size();

        // dp[i] = minimum cuts needed to partition s[i..n-1] into palindromic substrings
        vector<int> dp(size + 1, 0); // dp[n] = 0 by default (empty suffix needs 0 cuts)

        // Start filling dp from the end of the string toward the beginning
        for (int i = size - 1; i >= 0; i--) {
            int miniCuts = INT_MAX;

            // Try every possible end index j where s[i..j] is a palindrome
            for (int j = i; j < size; j++) {
                if (isPalindrome(s, i, j)) {
                    // If s[i..j] is a palindrome, 1 cut (after j) + solve the rest
                    int currCuts = 1 + dp[j + 1];
                    miniCuts = min(miniCuts, currCuts);
                }
            }

            // Store the minimum cuts for substring s[i..n-1]
            dp[i] = miniCuts;
        }

        // We do one extra cut than needed, so subtract 1
        return dp[0] - 1;
    }
};

Complexity Analysis:

• Time Complexity:O(n^3)
  • The outer loop runs O(n) times
  • The inner loop runs up to O(n) for each i.
  • The isPalindrome(s, i, j) runs in O(n) time in the worst case
  • Total Time: O(n^3)
• Space Complexity:O(n)
  • dp[] take O(n) space