Minimum cuts required to convert a palindromic string to a different palindromic string | CPP program to solve the above problem ; Recursive function to find minimum number of cuts if length of string is even ; If length is odd then return 2 ; To check if half of palindromic string is itself a palindrome ; If not then return 1 ; Else call function with half palindromic string ; Function to find minimum number of cuts If length of string is odd ; If length is <= 3 then it is impossible ; Array to store frequency of characters ; Store count of characters in a array ; Condition for edge cases ; If length is even ; If length is odd ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solveEven ( string s ) { if ( s . length ( ) % 2 == 1 ) return 2 ; string ls = s . substr ( 0 , s . length ( ) / 2 ) ; string rs = s . substr ( s . length ( ) / 2 , s . length ( ) ) ; if ( ls != rs ) return 1 ; return solveEven ( ls ) ; } int solveOdd ( string s ) { return 2 ; } int solve ( string s ) { if ( s . length ( ) <= 3 ) { return -1 ; } int cnt [ 25 ] = { } ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { cnt [ s [ i ] - ' a ' ] ++ ; } if ( * max_element ( cnt , cnt + 25 ) >= s . length ( ) - 1 ) { return -1 ; } if ( s . length ( ) % 2 == 0 ) return solveEven ( s ) ; if ( s . length ( ) % 2 == 1 ) return solveOdd ( s ) ; } int main ( ) { string s = " nolon " ; cout << solve ( s ) ; return 0 ; }