3132333435363738394041424344454647484950515253545556575859

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

class Solution{
private:
    // Function to check if 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 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 the result
        return minCost;
    }
public:
    /* Main function to find the minimum number
    of partitions for palindrome partitioning.*/
    int minCut(string s) {
        int n = s.size();
        
        /* Calling recursive function and subtracting 
        1 as it counts partitions, not cuts.*/
        return minPartitions(0, n, s) - 1;
    }
};

int main() {
    string str = "BABABCBADCEDE";

    //Create an instance of Solution class
    Solution sol;
    
    cout << "The minimum number of partitions: " << sol.minCut(str) << "\n";
    return 0;
}

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

import java.util.*;

class Solution {
    // Function to check if substring is a palindrome.
    private boolean isPalindrome(int i, int j, String s) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }

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

        int minCost = Integer.MAX_VALUE;
        /* 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 =