Palindrome Partitioning – II | Front Partition : DP 53

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.

Examples
Example 1:
Input: s = “bababcbadcede”
Output: 4
Explanation: If we do 4 partitions in the following way, 
each substring of the partition will be a palindrome.
bab | abcba | d | c | ede
Input: s = "aab"
Output: 1
Explanation: If we do 1 partition in the following way, 
each substring of the partition will be a palindrome.
aa | b
Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Recursive approach Memoization approach Tabulation Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Recursive Approach
Algorithm / Intuition

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 the following:
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. 

The following illustration will depict the process of partitioning:

We have found the right approach so far. Now, let us quickly discuss the rules to solve this problem:

  1. Express everything(i.e. the given string) in terms of the index.
  2. Try all partitions.
  3. Return the best possible answer of all partitions (the answer that comes after dividing the problem into subproblems and solving them recursively).
    Derive the base case as well.

Express everything(i.e. 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. The function will look like the following:

Try 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:

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.

The recurrence logic will be the following:

Note 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).

Note: If you wish to see the dry run of the above approach, you can watch the video attached to this article.

Approach

The recursive algorithm steps are as follows:

  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

#include <bits/stdc++.h>
using namespace std;

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

// Recursive function to find the minimum number of partitions to make palindromes.
int minPartitions(int i, int n, string &str) {
    // Base case: If we've reached the end of the string.
    if (i == n) return 0;

    int minCost = INT_MAX;
    // Consider all possible substrings starting from the current index.
    for (int j = i; j < n; j++) {
        if (isPalindrome(i, j, str)) {
            // If the substring is a palindrome, calculate the cost and minimize it.
            int cost = 1 + minPartitions(j + 1, n, str);
            minCost = min(minCost, cost);
        }
    }
    return minCost;
}

// Main function to find the minimum number of partitions for palindrome partitioning.
int palindromePartitioning(string str) {
    int n = str.size();
    // Calling the recursive function and subtracting 1 as it counts partitions, not cuts.
    return minPartitions(0, n, str) - 1;
}

int main() {
    string str = "BABABCBADCEDE";
    int partitions = palindromePartitioning(str);
    cout << "The minimum number of partitions: " << partitions << "\n";
    return 0;
}



public class PalindromePartitioning {
    static boolean isPalindrome(int i, int j, String s) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }

    static int f(int i, int n, String str) {
        // Base case:
        if (i == n) return 0;

        int minCost = Integer.MAX_VALUE;
        // String[i...j]
        for (int j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                int cost = 1 + f(j + 1, n, str);
                minCost = Math.min(minCost, cost);
            }
        }
        return minCost;
    }

    static int palindromePartitioning(String str) {
        int n = str.length();
        return f(0, n, str) - 1;
    }

    public static void main(String[] args) {
        String str = "BABABCBADCEDE";
        int partitions = palindromePartitioning(str);
        System.out.println("The minimum number of partitions: " + partitions);
    }
}




def is_palindrome(i, j, s):
    # Helper function to check if a substring s[i...j] is a palindrome
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def f(i, n, s):
    # Base case: If we reach the end of the string, no further partition is needed
    if i == n:
        return 0

    min_cost = float('inf')
    
    # Iterate over possible substrings starting from index i
    for j in range(i, n):
        if is_palindrome(i, j, s):
            # If s[i...j] is a palindrome, calculate the cost
            cost = 1 + f(j + 1, n, s)
            min_cost = min(min_cost, cost)

    return min_cost

def palindrome_partitioning(s):
    # Main function to find the minimum number of partitions
    n = len(s)
    return f(0, n, s) - 1  # Subtract 1 to exclude the initial unpartitioned string

if __name__ == "__main__":
    str = "BABABCBADCEDE"
    partitions = palindrome_partitioning(str)
    print("The minimum number of partitions:", partitions)



// Function to check if a substring from index i to j is a palindrome
function isPalindrome(i, j, s) {
    while (i < j) {
        if (s[i] !== s[j]) return false;
        i++;
        j--;
    }
    return true;
}

// Function to find the minimum number of partitions needed to make palindromes
function palindromePartitioning(str) {
    // Function f to recursively calculate the minimum number of partitions
    function f(i, n, str) {
        // Base case: If i reaches the end of the string, return 0
        if (i === n) return 0;

        let minCost = Infinity;

        // Check all possible substrings starting from index i
        for (let j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                // Calculate the cost for the current partition
                const cost = 1 + f(j + 1, n, str);
                minCost = Math.min(minCost, cost);
            }
        }

        return minCost;
    }

    const n = str.length;

    // Call the recursive function with initial values and subtract 1 from the result
    return f(0, n, str) - 1;
}

// Main function
function main() {
    const str = "BABABCBADCEDE";
    const partitions = palindromePartitioning(str);
    console.log("The minimum number of partitions:", partitions);
}

// Call the main function
main();

The minimum number of partitions: 4 (Given string: “BABABCBADCEDE”)

Complexity Analysis

Time Complexity: Exponential

Memoization Approach
Algorithm / Intuition

Steps to memoize the recursive solution:

  1. Create a 1D dp array of size [n] i can range from 0 to n-1. So we take the size n.
  2. We initialize the dp array to -1.
  3. Whenever we want to find the answer to a particular parameter (say f(i)), we first check whether the answer is already calculated using the dp array(i.e dp[i] != -1 ). If yes, simply return the value from the dp array.
  4. If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i] to the solution we get.
Code


#include <bits/stdc++.h>
using namespace std;

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

// Recursive function to find the minimum number of partitions to make palindromes.
int minPartitions(int i, int n, string &str, vector<int> &dp) {
    // Base case: If we've reached the end of the string.
    if (i == n) return 0;

    if (dp[i] != -1) return dp[i];
    int minCost = INT_MAX;
    // Consider all possible substrings starting from the current index.
    for (int j = i; j < n; j++) {
        if (isPalindrome(i, j, str)) {
            // If the substring is a palindrome, calculate the cost and minimize it.
            int cost = 1 + minPartitions(j + 1, n, str, dp);
            minCost = min(minCost, cost);
        }
    }
    return dp[i] = minCost;
}

// Main function to find the minimum number of partitions for palindrome partitioning.
int palindromePartitioning(string str) {
    int n = str.size();
    vector<int> dp(n, -1);
    // Calling the recursive function and subtracting 1 as it counts partitions, not cuts.
    return minPartitions(0, n, str, dp) - 1;
}

int main() {
    string str = "BABABCBADCEDE";
    int partitions = palindromePartitioning(str);
    cout << "The minimum number of partitions: " << partitions << "\n";
    return 0;
}




public class PalindromePartitioning {
    static boolean isPalindrome(int i, int j, String s) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }

    static int f(int i, int n, String str, int[] dp) {
        // Base case:
        if (i == n) return 0;

        if (dp[i] != -1) return dp[i];
        int minCost = Integer.MAX_VALUE;
        // String[i...j]
        for (int j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                int cost = 1 + f(j + 1, n, str, dp);
                minCost = Math.min(minCost, cost);
            }
        }
        return dp[i] = minCost;
    }

    static int palindromePartitioning(String str) {
        int n = str.length();
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return f(0, n, str, dp) - 1;
    }

    public static void main(String[] args) {
        String str = "BABABCBADCEDE";
        int partitions = palindromePartitioning(str);
        System.out.println("The minimum number of partitions: " + partitions);
    }
}




def is_palindrome(i, j, s):
    # Helper function to check if a substring s[i...j] is a palindrome
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def f(i, n, s, dp):
    # Base case: If we reach the end of the string, no further partition is needed
    if i == n:
        return 0

    if dp[i] != -1:
        return dp[i]
    
    min_cost = float('inf')
    
    # Iterate over possible substrings starting from index i
    for j in range(i, n):
        if is_palindrome(i, j, s):
            # If s[i...j] is a palindrome, calculate the cost
            cost = 1 + f(j + 1, n, s, dp)
            min_cost = min(min_cost, cost)

    dp[i] = min_cost
    return dp[i]

def palindrome_partitioning(s):
    # Main function to find the minimum number of partitions
    n = len(s)
    dp = [-1] * n  # Initialize a memoization array with -1
    return f(0, n, s, dp) - 1  # Subtract 1 to exclude the initial unpartitioned string

if __name__ == "__main__":
    str = "BABABCBADCEDE"
    partitions = palindrome_partitioning(str)
    print("The minimum number of partitions:", partitions)




// Function to check if a substring from index i to j is a palindrome
function isPalindrome(i, j, s) {
    while (i < j) {
        if (s[i] !== s[j]) return false;
        i++;
        j--;
    }
    return true;
}

// Function to find the minimum number of partitions needed to make palindromes
function palindromePartitioning(str) {
    // Function f with memoization
    function f(i, n, str, dp) {
        // Base case: If i reaches the end of the string, return 0
        if (i === n) return 0;

        // Check if the result for this subproblem is already computed
        if (dp[i] !== -1) return dp[i];

        let minCost = Infinity;

        // Check all possible substrings starting from index i
        for (let j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                // Calculate the cost for the current partition
                const cost = 1 + f(j + 1, n, str, dp);
                minCost = Math.min(minCost, cost);
            }
        }

        // Store the result in the memoization table
        dp[i] = minCost;
        return minCost;
    }

    const n = str.length;
    const dp = new Array(n).fill(-1);

    // Call the recursive function with initial values and subtract 1 from the result
    return f(0, n, str, dp) - 1;
}

// Main function
function main() {
    const str = "BABABCBADCEDE";
    const partitions = palindromePartitioning(str);
    console.log("The minimum number of partitions:", partitions);
}

// Call the main function
main();

The minimum number of partitions: 4 (Given string: “BABABCBADCEDE”)

Complexity Analysis

Time Complexity: O(N2)
Reason: There are a total of N states and inside each state, a loop of size N(apparently) is running.

Space Complexity: O(N) + Auxiliary stack space O(N)
Reason: The first O(N) is for the dp array of size N.

Tabulation Approach
Algorithm / Intuition

Tabulation:

  1. First of all, we handle the base case. If (i == n) we return 0. To cover this case we can initialize the entire dp array with 0.
    Here, as we are checking 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. 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.
  3. Next, we copy down the recursive logic(recurrence) inside the loop.
Code

#include <bits/stdc++.h>
using namespace std;

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

// Function to find the minimum number of partitions for palindrome partitioning.
int palindromePartitioning(string str) {
    int n = str.size();
    // Create a DP array to store the minimum number of partitions.
    vector<int> dp(n + 1, 0);
    dp[n] = 0; // Initialize the last element to 0.

    // Loop through the string in reverse order.
    for (int i = n - 1; i >= 0; i--) {
        int minCost = INT_MAX;
        // Consider all possible substrings starting from the current index.
        for (int j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                // If the substring is a palindrome, calculate the cost and minimize it.
                int cost = 1 + dp[j + 1];
                minCost = min(minCost, cost);
            }
        }
        dp[i] = minCost;
    }
    // Subtract 1 as it counts partitions, not cuts.
    return dp[0] - 1;
}

int main() {
    string str = "BABABCBADCEDE";
    int partitions = palindromePartitioning(str);
    cout << "The minimum number of partitions: " << partitions << "\n";
    return 0;
}



public class PalindromePartitioning {
    static boolean isPalindrome(int i, int j, String s) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }

    static int palindromePartitioning(String str) {
        int n = str.length();
        int[] dp = new int[n + 1];
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            int minCost = Integer.MAX_VALUE;
            // String[i...j]
            for (int j = i; j < n; j++) {
                if (isPalindrome(i, j, str)) {
                    int cost = 1 + dp[j + 1];
                    minCost = Math.min(minCost, cost);
                }
            }
            dp[i] = minCost;
        }
        return dp[0] - 1;
    }

    public static void main(String[] args) {
        String str = "BABABCBADCEDE";
        int partitions = palindromePartitioning(str);
        System.out.println("The minimum number of partitions: " + partitions);
    }
}



def is_palindrome(i, j, s):
    # Helper function to check if a substring s[i...j] is a palindrome
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def palindrome_partitioning(s):
    # Main function to find the minimum number of partitions
    n = len(s)
    dp = [0] * (n + 1)
    dp[n] = 0  # Initialize the last element of dp to 0
    for i in range(n - 1, -1, -1):  # Start from the second-to-last element and move backward
        min_cost = float('inf')
        # Iterate over possible substrings starting from index i
        for j in range(i, n):
            if is_palindrome(i, j, s):
                # If s[i...j] is a palindrome, calculate the cost
                cost = 1 + dp[j + 1]
                min_cost = min(min_cost, cost)
        dp[i] = min_cost

    return dp[0] - 1  # Subtract 1 to exclude the initial unpartitioned string

if __name__ == "__main__":
    str = "BABABCBADCEDE"
    partitions = palindrome_partitioning(str)
    print("The minimum number of partitions:", partitions)




// Function to check if a substring from index i to j is a palindrome
function isPalindrome(i, j, s) {
    while (i < j) {
        if (s[i] !== s[j]) return false;
        i++;
        j--;
    }
    return true;
}

// Function to find the minimum number of partitions needed to make palindromes
function palindromePartitioning(str) {
    const n = str.length;

    // Create an array dp to store the minimum number of partitions
    const dp = new Array(n + 1).fill(0);

    // Initialize dp[n] as 0 (no partitions needed for an empty string)
    dp[n] = 0;

    // Loop from the end of the string to the beginning
    for (let i = n - 1; i >= 0; i--) {
        let minCost = Infinity;

        // Check all possible substrings starting from index i
        for (let j = i; j < n; j++) {
            if (isPalindrome(i, j, str)) {
                // Calculate the cost for the current partition
                const cost = 1 + dp[j + 1];
                minCost = Math.min(minCost, cost);
            }
        }

        // Store the minimum cost for the current substring
        dp[i] = minCost;
    }

    // The result is stored in dp[0] - 1
    return dp[0] - 1;
}

// Main function
function main() {
    const str = "BABABCBADCEDE";
    const partitions = palindromePartitioning(str);
    console.log("The minimum number of partitions:", partitions);
}

// Call the main function
main();


The minimum number of partitions: 4 (Given string: “BABABCBADCEDE”)

Complexity Analysis

Time Complexity: O(N2)
Reason: There are a total of N states and inside each state a loop of size N(apparently) is running.

Space Complexity: O(N)
Reason: O(N) is for the dp array we have used.

Video Explanation

Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this articleIf you want to suggest any improvement/correction in this article please mail us at [email protected]