Minimum cuts required to convert a palindromic string to a different palindromic string | CPP program to solve the above problem ; Function to check if string is palindrome or not ; Function to check if it is possible to get result by making just one cut ; Appending last element in front ; Removing last element ; Checking whether string s2 is palindrome and different from s . ; 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 ; Return 1 if it is possible to get palindromic string in just one cut . Else we can always reached in two cuttings . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPalindrome ( string s ) { for ( int i = 0 ; i < s . length ( ) ; ++ i ) { if ( s [ i ] != s [ s . length ( ) - i - 1 ] ) { return false ; } } return true ; } bool ans ( string s ) { string s2 = s ; for ( int i = 0 ; i < s . length ( ) ; ++ i ) { s2 = s2 . back ( ) + s2 ; s2 . pop_back ( ) ; if ( s != s2 && isPalindrome ( s2 ) ) { return true ; } } return false ; } 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 ; } else { return ( ans ( s ) ? 1 : 2 ) ; } } int main ( ) { string s = " nolon " ; cout << solve ( s ) ; return 0 ; }