Minimum cuts required to convert a palindromic string to a different palindromic string | Java 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
import java . util . Arrays ; class GFG { static int solveEven ( String s ) { if ( s . length ( ) % 2 == 1 ) { return 2 ; } String ls = s . substring ( 0 , s . length ( ) / 2 ) ; String rs = s . substring ( s . length ( ) / 2 , s . length ( ) ) ; if ( ls != rs ) { return 1 ; } return solveEven ( ls ) ; } static int solveOdd ( String s ) { return 2 ; } static int solve ( String s ) { if ( s . length ( ) <= 3 ) { return - 1 ; } int cnt [ ] = new int [ 25 ] ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { cnt [ s . charAt ( i ) - ' a ' ] ++ ; } if ( Arrays . stream ( cnt ) . max ( ) . getAsInt ( ) >= s . length ( ) - 1 ) { return - 1 ; } if ( s . length ( ) % 2 == 0 ) { return solveEven ( s ) ; } if ( s . length ( ) % 2 == 1 ) { return solveOdd ( s ) ; } return Integer . MIN_VALUE ; } public static void main ( String [ ] args ) { String s = " nolon " ; System . out . println ( solve ( s ) ) ; } }