Given a string str, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome, the task is to find the minimum number of cuts needed for palindrome partitioning of the given string.
Palindrome Partition
Examples :
Input: str = “geek”
Output: 2
Explanation: We need to make minimum 2 cuts, i.e., “g ee k”Input: str = “aaaa”
Output: 0
Explanation: The string is already a palindrome.Input: str = “abcde”
Output: 4Input: str = “abbac”
Output: 1
Recursive Approach for Palindrome Partitioning:
This is the naive approach to solving the Palindrome Partitioning problem. In this approach, we will try to apply all possible partitions and at the end return the correct combination of partitions.
This approach is similar to that of Matrix Chain Multiplication problem.
In this approach, we recursively evaluate the following conditions:
- If the current string is a palindrome, then we simply return true, as Palindrome Partitioning is possible.
- Else, like the Matrix Chain Multiplication problem,
- we try making cuts at all possible places,
- recursively calculate the cost for each cut
- return the minimum value.
Below is the implementation of the above approach.
C++
// C++ Code for Palindrome Partitioning// Problem#include <bits/stdc++.h>using namespace std;// Function to Check if a substring is a palindromebool isPalindrome(string String, int i, int j){ while (i < j) { if (String[i] != String[j]) return false; i++; j--; } return true;}// Function to find the minimum number of cuts needed for// palindrome partitioningint minPalPartion(string String, int i, int j){ // Base case: If the substring is empty or a palindrome, // no cuts needed if (i >= j || isPalindrome(String, i, j)) return 0; int ans = INT_MAX, count; // Iterate through all possible partitions and find the // minimum cuts needed for (int k = i; k < j; k++) { count = minPalPartion(String, i, k) + minPalPartion(String, k + 1, j) + 1; ans = min(ans, count); } return ans;}// Driver codeint main(){ string str = "ababbbabbababa"; // Find the minimum cuts needed for palindrome // partitioning and display the result cout << "Min cuts needed for Palindrome Partitioning is " << minPalPartion(str, 0, str.length() - 1) << endl; return 0;} |
Java
//public class PalindromePartitioning { // Function to Check if a substring is a palindrome static boolean isPalindrome(String str, int i, int j) { while (i < j) { if (str.charAt(i) != str.charAt(j)) return false; i++; j--; } return true; } // Function to find the minimum number of cuts needed // for palindrome partitioning static int minPalPartition(String str, int i, int j) { // Base case: If the substring is empty or a // palindrome, no cuts needed if (i >= j || isPalindrome(str, i, j)) return 0; int minCuts = Integer.MAX_VALUE; // Iterate through all possible partitions and find // the minimum cuts needed for (int k = i; k < j; k++) { int cuts = minPalPartition(str, i, k) + minPalPartition(str, k + 1, j) + 1; minCuts = Math.min(minCuts, cuts); } return minCuts; } // Driver code public static void main(String[] args) { String str = "ababbbabbababa"; // Find the minimum cuts needed for palindrome // partitioning and display the result System.out.println( "Min cuts needed for Palindrome Partitioning is " + minPalPartition(str, 0, str.length() - 1)); }} |
Python3
# Function to Check if a substring is a palindromedef is_palindrome(string, i, j): while i < j: if string[i] != string[j]: return False i += 1 j -= 1 return True# Function to find the minimum number of cuts needed for palindrome partitioningdef min_pal_partition(string, i, j): # Base case: If the substring is empty or a palindrome, no cuts needed if i >= j or is_palindrome(string, i, j): return 0 ans = float('inf') # Iterate through all possible partitions and find the minimum cuts needed for k in range(i, j): count = min_pal_partition(string, i, k) + \ min_pal_partition(string, k + 1, j) + 1 ans = min(ans, count) return ans# Driver codeif __name__ == "__main__": str = "ababbbabbababa" # Find the minimum cuts needed for palindrome partitioning and display the result print("Min cuts needed for Palindrome Partitioning is", min_pal_partition(str, 0, len(str) - 1)) |
C#
using System;// Function to Check if a substring is a palindromepublic class PalindromePartitioning { // Function to Check if a substring is a palindrome static bool IsPalindrome(string str, int i, int j) { while (i < j) { if (str[i] != str[j]) return false; i++; j--; } return true; } // Function to find the minimum number of cuts needed // for palindrome partitioning static int MinPalPartition(string str, int i, int j) { // Base case: If the substring is empty or a // palindrome, no cuts needed if (i >= j || IsPalindrome(str, i, j)) return 0; int minCuts = int.MaxValue; // Iterate through all possible partitions and find // the minimum cuts needed for (int k = i; k < j; k++) { int cuts = MinPalPartition(str, i, k) + MinPalPartition(str, k + 1, j) + 1; minCuts = Math.Min(minCuts, cuts); } return minCuts; } // Driver code public static void Main(string[] args) { string str = "ababbbabbababa"; // Find the minimum cuts needed for palindrome // partitioning and display the result Console.WriteLine( "Min cuts needed for Palindrome Partitioning is " + MinPalPartition(str, 0, str.Length - 1)); }} |
Javascript
<script>// Javascript code for Palindrome// Partitioning Problem// Function to Check if a substring is a palindromefunction isPalindrome(String, i, j){ while (i < j) { if (String[i] != String[j]) return false; i++; j--; } return true;}// Function to find the minimum number of cuts needed// for palindrome partitioningfunction minPalPartion(String, i, j){ // Base case: If the substring is empty or a palindrome, // no cuts needed if (i >= j || isPalindrome(String, i, j)) return 0; let ans = Number.MAX_VALUE, count; // Iterate through all possible partitions and find the // minimum cuts needed for(let k = i; k < j; k++) { count = minPalPartion(String, i, k) + minPalPartion(String, k + 1, j) + 1; ans = Math.min(ans, count); } return ans;}// Driver codelet str = "ababbbabbababa";// Find the minimum cuts needed for palindrome// partitioning and display the resultdocument.write("Min cuts needed for " + "Palindrome Partitioning is " + minPalPartion(str, 0, str.length - 1));</script> |
Output
Min cuts needed for Palindrome Partitioning is 3
Time Complexity: O(2n)
Auxiliary Space: O(n)
Optimising Overlapping Sub-problems in Recursive Approach for Palindrome Partitioning in (O(n3)):
The above recursive approach has overlapping subproblems, leading to redundant computations thereby resulting in exponential time complexity. This redundant computation can be solved by using Dynamic programming approach.
Here, we can use two 2D array C[][] and P[][], for storing the computed result.
- C[i][j] stores the minimum number of cuts needed for the substring str[i..j],
- while P[i][j] stores whether the substring str[i..j] is a palindrome or not.
- It starts with smaller substrings and gradually builds up to the entire string.
Below is the implementation of the above approach:
C++
// Dynamic Programming Solution for// Palindrome Partitioning Problem#include <bits/stdc++.h>using namespace std;// Returns the minimum number of cuts// needed to partition a string// such that every part is a palindromeint minPalPartion(string str){ // Get the length of the string int n = str.length(); // Create two arrays to build the solution in bottom up // manner // C[i][j] = Minimum number of cuts needed for // palindrome partitioning of substring str[i..j] int C[n][n]; // P[i][j] = true if substring str[i..j] is palindrome, // else false bool P[n][n]; // Note that C[i][j] is 0 if P[i][j] is true // Every substring of length 1 is a palindrome for (int i = 0; i < n; i++) { P[i][i] = true; C[i][i] = 0; } // L is substring length. Build the // solution in bottom up manner by // considering all substrings of // length starting from 2 to n. // The loop structure is same as Matrix // Chain Multiplication problem for (int L = 2; L <= n; L++) { // For substring of length L, set // different possible starting indexes for (int i = 0; i < n - L + 1; i++) { int j = i + L - 1; // Set ending index // If L is 2, then we just need to // compare two characters. Else // need to check two corner characters // and value of P[i+1][j-1] if (L == 2) P[i][j] = (str[i] == str[j]); else P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1]; // IF str[i..j] is palindrome, then C[i][j] is 0 if (P[i][j] == true) C[i][j] = 0; else { // Make a cut at every possible // location starting from i to j, // and get the minimum cost cut. C[i][j] = INT_MAX; for (int k = i; k <= j - 1; k++) C[i][j] = min( C[i][j], C[i][k] + C[k + 1][j] + 1); } } } // Return the min cut value for // complete string. i.e., str[0..n-1] return C[0][n - 1];}// Driver codeint main(){ string str = "ababbbabbababa"; cout << "Min cuts needed for Palindrome" " Partitioning is " << minPalPartion(str); return 0;}// This code is contributed by rathbhupendra |
C
// Dynamic Programming Solution for Palindrome Partitioning// Problem#include <limits.h>#include <stdio.h>#include <string.h>// A utility function to get minimum of two integersint min(int a, int b) { return (a < b) ? a : b; }// Returns the minimum number of cuts needed to partition a// string such that every part is a palindromeint minPalPartion(char* str){ // Get the length of the string int n = strlen(str); /* Create two arrays to build the solution in bottom up manner C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring str[i..j] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i][j] is 0 if P[i][j] is true */ int C[n][n]; bool P[n][n]; int i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i = 0; i < n; i++) { P[i][i] = true; C[i][i] = 0; } /* L is substring length. Build the solution in bottom up manner by considering all substrings of length starting from 2 to n. The loop structure is same as Matrix Chain Multiplication problem ( See https:// www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ )*/ for (L = 2; L <= n; L++) { // For substring of length L, set different possible // starting indexes for (i = 0; i < n - L + 1; i++) { j = i + L - 1; // Set ending index // If L is 2, then we just need to compare two // characters. Else need to check two corner // characters and value of P[i+1][j-1] if (L == 2) P[i][j] = (str[i] == str[j]); else P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1]; // IF str[i..j] is palindrome, then C[i][j] is 0 if (P[i][j] == true) C[i][j] = 0; else { // Make a cut at every possible location // starting from i to j, and get the minimum // cost cut. C[i][j] = INT_MAX; for (k = i; k <= j - 1; k++) C[i][j] = min( C[i][j], C[i][k] + C[k + 1][j] + 1); } } } // Return the min cut value for complete string. i.e., // str[0..n-1] return C[0][n - 1];}// Driver program to test above functionint main(){ char str[] = "ababbbabbababa"; printf( "Min cuts needed for Palindrome Partitioning is %d", minPalPartion(str)); return 0;} |
Java
// Java Code for Palindrome Partitioning// Problempublic class GFG { // Returns the minimum number of cuts needed // to partition a string such that every // part is a palindrome static int minPalPartion(String str) { // Get the length of the string int n = str.length(); /* Create two arrays to build the solution in bottom up manner C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring str[i..j] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i][j] is 0 if P[i][j] is true */ int[][] C = new int[n][n]; boolean[][] P = new boolean[n][n]; int i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i = 0; i < n; i++) { P[i][i] = true; C[i][i] = 0; } /* L is substring length. Build the solution in bottom up manner by considering all substrings of length starting from 2 to n. The loop structure is same as Matrix Chain Multiplication problem ( See https:// www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ )*/ for (L = 2; L <= n; L++) { // For substring of length L, set different // possible starting indexes for (i = 0; i < n - L + 1; i++) { j = i + L - 1; // Set ending index // If L is 2, then we just need to // compare two characters. Else need to // check two corner characters and value // of P[i+1][j-1] if (L == 2) P[i][j] = (str.charAt(i) == str.charAt(j)); else P[i][j] = (str.charAt(i) == str.charAt(j)) && P[i + 1][j - 1]; // IF str[i..j] is palindrome, then // C[i][j] is 0 if (P[i][j] == true) C[i][j] = 0; else { // Make a cut at every possible // localtion starting from i to j, // and get the minimum cost cut. C[i][j] = Integer.MAX_VALUE; for (k = i; k <= j - 1; k++) C[i][j] = Integer.min( C[i][j], C[i][k] + C[k + 1][j] + 1); } } } // Return the min cut value for complete // string. i.e., str[0..n-1] return C[0][n - 1]; } // Driver program to test above function public static void main(String args[]) { String str = "ababbbabbababa"; System.out.println("Min cuts needed for " + "Palindrome Partitioning is " + minPalPartion(str)); }}// This code is contributed by Sumit Ghosh |
Python3
# Dynamic Programming Solution for# Palindrome Partitioning Problem# Returns the minimum number of# cuts needed to partition a string# such that every part is a palindromedef minPalPartion(str): # Get the length of the string n = len(str) # Create two arrays to build the # solution in bottom up manner # C[i][j] = Minimum number of cuts # needed for palindrome # partitioning of substring str[i..j] # P[i][j] = true if substring str[i..j] # is palindrome, else false. Note that # C[i][j] is 0 if P[i][j] is true C = [[0 for i in range(n)] for i in range(n)] P = [[False for i in range(n)] for i in range(n)] # different looping variables j = 0 k = 0 L = 0 # Every substring of length # 1 is a palindrome for i in range(n): P[i][i] = True C[i][i] = 0 # L is substring length. Build the # solution in bottom-up manner by # considering all substrings of # length starting from 2 to n. # The loop structure is the same as # Matrix Chain Multiplication problem # (See https://www.geeksforgeeks.org / matrix-chain-multiplication-dp-8/ ) for L in range(2, n + 1): # For substring of length L, set # different possible starting indexes for i in range(n - L + 1): j = i + L - 1 # Set ending index # If L is 2, then we just need to # compare two characters. Else # need to check two corner characters # and value of P[i + 1][j-1] if L == 2: P[i][j] = (str[i] == str[j]) else: P[i][j] = ((str[i] == str[j]) and P[i + 1][j - 1]) # IF str[i..j] is palindrome, # then C[i][j] is 0 if P[i][j] == True: C[i][j] = 0 else: # Make a cut at every possible # location starting from i to j, # and get the minimum cost cut. C[i][j] = 100000000 for k in range(i, j): C[i][j] = min(C[i][j], C[i][k] + C[k + 1][j] + 1) # Return the min cut value for # complete string. i.e., str[0..n-1] return C[0][n - 1]# Driver codestr = "ababbbabbababa"print('Min cuts needed for Palindrome Partitioning is', minPalPartion(str))# This code is contributed# by Sahil shelangia |
C#
// C# Code for Palindrome Partitioning// Problemusing System;class GFG { // Returns the minimum number of cuts needed // to partition a string such that every // part is a palindrome static int minPalPartion(String str) { // Get the length of the string int n = str.Length; /* Create two arrays to build the solution in bottom up manner C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring str[i..j] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i][j] is 0 if P[i][j] is true */ int[, ] C = new int[n, n]; bool[, ] P = new bool[n, n]; int i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i = 0; i < n; i++) { P[i, i] = true; C[i, i] = 0; } /* L is substring length. Build the solution in bottom up manner by considering all substrings of length starting from 2 to n. The loop structure is same as Matrix Chain Multiplication problem ( See https:// www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ )*/ for (L = 2; L <= n; L++) { // For substring of length L, set different // possible starting indexes for (i = 0; i < n - L + 1; i++) { j = i + L - 1; // Set ending index // If L is 2, then we just need to // compare two characters. Else need to // check two corner characters and value // of P[i+1][j-1] if (L == 2) P[i, j] = (str[i] == str[j]); else P[i, j] = (str[i] == str[j]) && P[i + 1, j - 1]; // IF str[i..j] is palindrome, then // C[i][j] is 0 if (P[i, j] == true) C[i, j] = 0; else { // Make a cut at every possible // location starting from i to j, // and get the minimum cost cut. C[i, j] = int.MaxValue; for (k = i; k <= j - 1; k++) C[i, j] = Math.Min( C[i, j], C[i, k] + C[k + 1, j] + 1); } } } // Return the min cut value for complete // string. i.e., str[0..n-1] return C[0, n - 1]; } // Driver program public static void Main() { String str = "ababbbabbababa"; Console.Write("Min cuts needed for " + "Palindrome Partitioning is " + minPalPartion(str)); }}// This code is contributed by Sam007 |
Javascript
<script>// javascript Code for Palindrome Partitioning// Problem // Returns the minimum number of cuts needed // to partition a string such that every // part is a palindrome function minPalPartion( str) { // Get the length of the string var n = str.length; /* * Create two arrays to build the solution in bottom up manner C[i][j] = Minimum * number of cuts needed for palindrome partitioning of substring str[i..j] * P[i][j] = true if substring str[i..j] is palindrome, else false Note that * C[i][j] is 0 if P[i][j] is true */ var C = Array(n).fill().map(()=>Array(n).fill(0)); var P = Array(n).fill().map(()=>Array(n).fill(false)); var i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i = 0; i < n; i++) { P[i][i] = true; C[i][i] = 0; } /* * L is substring length. Build the solution in bottom up manner by considering * all substrings of length starting from 2 to n. The loop structure is same as * Matrix Chain Multiplication problem ( See https:// * www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ ) */ for (L = 2; L <= n; L++) { // For substring of length L, set different // possible starting indexes for (i = 0; i < n - L + 1; i++) { j = i + L - 1; // Set ending index // If L is 2, then we just need to // compare two characters. Else need to // check two corner characters and value // of P[i+1][j-1] if (L == 2) P[i][j] = (str.charAt(i) == str.charAt(j)); else P[i][j] = (str.charAt(i) == str.charAt(j)) && P[i + 1][j - 1]; // IF str[i..j] is palindrome, then // C[i][j] is 0 if (P[i][j] == true) C[i][j] = 0; else { // Make a cut at every possible // localtion starting from i to j, // and get the minimum cost cut. C[i][j] = Number.MAX_VALUE; for (k = i; k <= j - 1; k++) C[i][j] = Math.min(C[i][j], C[i][k] + C[k + 1][j] + 1); } } } // Return the min cut value for complete // string. i.e., str[0..n-1] return C[0][n - 1]; } // Driver program to test above function var str = "ababbbabbababa"; document.write("Min cuts needed for " + "Palindrome Partitioning is " + minPalPartion(str));// This code is contributed by Rajput-Ji </script> |
PHP
<?php // Dynamic Programming Solution for Palindrome Partitioning Problem // Returns the minimum number of cuts needed to partition a string// such that every part is a palindromefunction minPalPartion($str){ // Get the length of the string $n = strlen($str); /* Create two arrays to build the solution in bottom up manner C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring str[i..j] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i][j] is 0 if P[i][j] is true */ $C = array_fill(0, $n, array_fill(0, $n, NULL)); $P = array_fill(false, $n, array_fill(false, $n, NULL)); // Every substring of length 1 is a palindrome for ($i=0; $i<$n; $i++) { $P[$i][$i] = true; $C[$i][$i] = 0; } /* L is substring length. Build the solution in a bottom-up manner by considering all substrings of length starting from 2 to n. The loop structure is same as Matrix Chain Multiplication problem ( for ($L=2; $L<=$n; $L++) { // For substring of length L, set different possible starting indexes for ($i=0; $i<$n-$L+1; $i++) { $j = $i+$L-1; // Set ending index // If L is 2, then we just need to compare two characters. Else // need to check two corner characters and value of P[i+1][j-1] if ($L == 2) $P[$i][$j] = ($str[$i] == $str[$j]); else $P[$i][$j] = ($str[$i] == $str[$j]) && $P[$i+1][$j-1]; // IF str[i..j] is palindrome, then C[i][j] is 0 if ($P[$i][$j] == true) $C[$i][$j] = 0; else { // Make a cut at every possible location starting from i to j, // and get the minimum cost cut. $C[$i][$j] = PHP_INT_MAX; for ($k=$i; $k<=$j-1; $k++) $C[$i][$j] = min ($C[$i][$j], $C[$i][$k] + $C[$k+1][$j]+1); } } } // Return the min cut value for complete string. i.e., str[0..n-1] return $C[0][$n-1];} // Driver program to test the above function$str = "ababbbabbababa";echo "Min cuts needed for Palindrome Partitioning is " .minPalPartion($str);return 0;?> |
Output
Min cuts needed for Palindrome Partitioning is 3
Time Complexity: O(n3)
Auxiliary Space: O(n2)
Dynamic Programming Approach for Palindrome Partitioning in (O(n2)):
The problem can be solved by finding the suffix starting from j and ending at index i, (1 <= j <= i <= n – 1), which are palindromes. Hence, we can make a cut here that requires 1 + min cut from rest substring [0, j – 1]. For all such palindromic suffixes starting at j and ending at i, keep minimising in minCutDp[i]. Similarly, we need to compute results for all such i. (1 <= i <= n – 1) and finally, minCutDp[n – 1] will be the minimum number of cuts needed for palindrome partitioning of the given string.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to generate all possible palindromic substringbool generatePalindrome(string& s, vector<vector<bool> >& pal){ int n = s.size(); // Initialize the palindrome matrix for single // characters for (int i = 0; i < n; i++) { pal[i][i] = true; } // Iterate over different lengths of substrings for (int len = 2; len <= n; len++) { // Iterate over the starting positions of substrings // of current length for (int i = 0; i <= n - len; i++) { // Calculate the ending position of the // substring int j = i + len - 1; // Check if the characters at the starting and // ending positions are equal and if the // substring between them is a palindrome or a // single character if (s[i] == s[j] && (len == 2 || pal[i + 1][j - 1])) { // Mark the substring from i to j as a // palindrome pal[i][j] = true; } } }}// Function to calculate the minimum number of cuts required// to make all substrings of 's' palindromicint minCut(string s){ if (s.empty()) return 0; int n = s.size(); // 2D vector to store whether substring [i, j] is a // palindrome vector<vector<bool> > pal(n, vector<bool>(n, false)); generatePalindrome(s, pal); // vector to store minimum cuts required to make // substring [i, n-1] palindromic vector<int> minCutDp(n, INT_MAX); // There is no cut required for single character // as it is always palindrome minCutDp[0] = 0; // Iterate over the given string for (int i = 1; i < n; i++) { // Check if string 0 to i is palindrome. // Then minCut require will be 0. if (pal[0][i]) { minCutDp[i] = 0; } else { for (int j = i; j >= 1; j--) { // If s[i] and s[j] are equal and the inner // substring [i+1, j-1] is a palindrome or // it has a length of 1 if (pal[j][i]) { // Update the minimum cuts required if // cutting at position 'j+1' results in // a smaller value if (minCutDp[j - 1] + 1 < minCutDp[i]) minCutDp[i] = minCutDp[j - 1] + 1; } } } } // Return the minimum cuts required for the entire // string 's' return minCutDp[n - 1];}int main(){ string str = "ababbbabbababa"; int cuts = minCut(str); cout << "Minimum cuts required: " << cuts << endl; return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to generate all possible palindromic // substrings static boolean generatePalindrome(String s, boolean[][] pal) { int n = s.length(); // Initialize the palindrome matrix for single // characters for (int i = 0; i < n; i++) { pal[i][i] = true; } // Iterate over different lengths of substrings for (int len = 2; len <= n; len++) { // Iterate over the starting positions of // substrings of current length for (int i = 0; i <= n - len; i++) { // Calculate the ending position of the // substring int j = i + len - 1; // Check if the characters at the starting // and ending positions are equal and if the // substring between them is a palindrome or // a single character if (s.charAt(i) == s.charAt(j) && (len == 2 || pal[i + 1][j - 1])) { // Mark the substring from i to j as a // palindrome pal[i][j] = true; } } } return true; } // Function to calculate the minimum number of cuts // required to make all substrings of 's' palindromic static int minCut(String s) { if (s.isEmpty()) return 0; int n = s.length(); // 2D array to store whether substring [i, j] is a // palindrome boolean[][] pal = new boolean[n][n]; generatePalindrome(s, pal); // Array to store minimum cuts required to make // substring [i, n-1] palindromic int[] minCutDp = new int[n]; Arrays.fill(minCutDp, Integer.MAX_VALUE); // There is no cut required for single character // as it is always palindrome minCutDp[0] = 0; // Iterate over the given string for (int i = 1; i < n; i++) { // Check if string 0 to i is palindrome. // Then minCut require will be 0. if (pal[0][i]) { minCutDp[i] = 0; } else { for (int j = i; j >= 1; j--) { // If s[i] and s[j] are equal and the // inner substring [i+1, j-1] is a // palindrome or it has a length of 1 if (pal[j][i]) { // Update the minimum cuts required // if cutting at position 'j+1' // results in a smaller value if (minCutDp[j - 1] + 1 < minCutDp[i]) minCutDp[i] = minCutDp[j - 1] + 1; } } } } // Return the minimum cuts required for the entire // string 's' return minCutDp[n - 1]; } public static void main(String[] args) { String str = "ababbbabbababa"; int cuts = minCut(str); System.out.println("Minimum cuts required: " + cuts); }} |
Python3
def generate_palindrome(s, pal): n = len(s) # Initialize the palindrome matrix for single characters for i in range(n): pal[i][i] = True # Iterate over different lengths of substrings for length in range(2, n + 1): # Iterate over the starting positions of substrings of current length for i in range(n - length + 1): # Calculate the ending position of the substring j = i + length - 1 # Check if the characters at the starting and ending positions are equal # and if the substring between them is a palindrome or a single character if s[i] == s[j] and (length == 2 or pal[i + 1][j - 1]): # Mark the substring from i to j as a palindrome pal[i][j] = Truedef min_cut(s): if not s: return 0 n = len(s) # 2D list to store whether substring [i, j] is a palindrome pal = [[False] * n for _ in range(n)] generate_palindrome(s, pal) # List to store minimum cuts required to make substring [i, n-1] palindromic min_cut_dp = [float('inf')] * n # There is no cut required for a single character as it is always a palindrome min_cut_dp[0] = 0 # Iterate over the given string for i in range(1, n): # Check if string 0 to i is a palindrome. Then minCut required will be 0. if pal[0][i]: min_cut_dp[i] = 0 else: for j in range(i, 0, -1): # If s[i] and s[j] are equal and the inner substring [i+1, j-1] # is a palindrome or it has a length of 1 if pal[j][i]: # Update the minimum cuts required if cutting at position 'j+1' results in a smaller value if min_cut_dp[j - 1] + 1 < min_cut_dp[i]: min_cut_dp[i] = min_cut_dp[j - 1] + 1 # Return the minimum cuts required for the entire string 's' return min_cut_dp[n - 1]# Driver codeif __name__ == "__main__": str = "ababbbabbababa" cuts = min_cut(str) print("Minimum cuts required:", cuts) |
C#
using System;class Program { // Function to generate all possible palindromic // substrings static void GeneratePalindrome(string s, bool[, ] pal) { int n = s.Length; // Initialize the palindrome matrix for single // characters for (int i = 0; i < n; i++) { pal[i, i] = true; } // Iterate over different lengths of substrings for (int len = 2; len <= n; len++) { // Iterate over the starting positions of // substrings of current length for (int i = 0; i <= n - len; i++) { // Calculate the ending position of the // substring int j = i + len - 1; // Check if the characters at the starting // and ending positions are equal and if the // substring between them is a palindrome or // a single character if (s[i] == s[j] && (len == 2 || pal[i + 1, j - 1])) { // Mark the substring from i to j as a // palindrome pal[i, j] = true; } } } } // Function to calculate the minimum number of cuts // required to make all substrings of 's' palindromic static int MinCut(string s) { if (string.IsNullOrEmpty(s)) return 0; int n = s.Length; // 2D array to store whether substring [i, j] is a // palindrome bool[, ] pal = new bool[n, n]; GeneratePalindrome(s, pal); // Array to store minimum cuts required to make // substring [i, n-1] palindromic int[] minCutDp = new int[n]; for (int i = 0; i < n; i++) { minCutDp[i] = int.MaxValue; } // There is no cut required for single character as // it is always a palindrome minCutDp[0] = 0; // Iterate over the given string for (int i = 1; i < n; i++) { // Check if string 0 to i is a palindrome. Then // minCut required will be 0. if (pal[0, i]) { minCutDp[i] = 0; } else { for (int j = i; j >= 1; j--) { // If s[i] and s[j] are equal and the // inner substring [i+1, j-1] is a // palindrome or it has a length of 1 if (pal[j, i]) { // Update the minimum cuts required // if cutting at position 'j+1' // results in a smaller value if (minCutDp[j - 1] + 1 < minCutDp[i]) minCutDp[i] = minCutDp[j - 1] + 1; } } } } // Return the minimum cuts required for the entire // string 's' return minCutDp[n - 1]; } static void Main() { string str = "ababbbabbababa"; int cuts = MinCut(str); Console.WriteLine("Minimum cuts required: " + cuts); }} |
Javascript
// JavaScript Code for the above approachfunction generatePalindrome(s, pal) { const n = s.length; // Initialize the palindrome matrix for single characters for (let i = 0; i < n; i++) { pal[i][i] = true; } // Iterate over different lengths of substrings for (let len = 2; len <= n; len++) { // Iterate over the starting positions of substrings of current length for (let i = 0; i <= n - len; i++) { // Calculate the ending position of the substring const j = i + len - 1; // Check if the characters at the starting and ending positions are equal // and if the substring between them is a palindrome or a single character if (s[i] === s[j] && (len === 2 || pal[i + 1][j - 1])) { // Mark the substring from i to j as a palindrome pal[i][j] = true; } } }}function minCut(s) { if (!s) return 0; const n = s.length; // 2D array to store whether substring [i, j] is a palindrome const pal = Array.from({ length: n }, () => Array(n).fill(false)); generatePalindrome(s, pal); // Array to store the minimum cuts required to make substring [i, n-1] palindromic const minCutDp = Array(n).fill(Infinity); // There is no cut required for single character as it is always a palindrome minCutDp[0] = 0; // Iterate over the given string for (let i = 1; i < n; i++) { // Check if string 0 to i is a palindrome // Then minCut required will be 0. if (pal[0][i]) { minCutDp[i] = 0; } else { for (let j = i; j >= 1; j--) { // If s[i] and s[j] are equal and the inner substring [i+1, j-1] // is a palindrome or it has a length of 1 if (pal[j][i]) { // Update the minimum cuts required if cutting at position 'j+1' results in a smaller value if (minCutDp[j - 1] + 1 < minCutDp[i]) { minCutDp[i] = minCutDp[j - 1] + 1; } } } } } // Return the minimum cuts required for the entire string 's' return minCutDp[n - 1];}const str = "abbac";const cuts = minCut(str);document.write("Minimum cuts required:", cuts);// This code is contributed by Abhinav Mahajan (abhinav_m22) |
Output
Minimum cuts required: 3
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
