Split the given string into Odds : Digit DP | Java program to split the given string into odds ; Function to check whether a string is an odd number or not ; A function to find the minimum number of segments the given string can be divided such that every segment is a odd number ; Declare a splitdp [ ] array and initialize to - 1 ; Build the DP table in a bottom - up manner ; Initially Check if the entire prefix is odd ; If the Given Prefix can be split into Odds then for the remaining string from i to j Check if Odd . If yes calculate the minimum split till j ; To check if the substring from i to j is a odd number or not ; If it is an odd number , then update the dp array ; Return the minimum number of splits for the entire string ; Driver code
class GFG { static int checkOdd ( String number ) { int n = number . length ( ) ; int num = number . charAt ( n - 1 ) - '0' ; return ( num & 1 ) ; } static int splitIntoOdds ( String number ) { int numLen = number . length ( ) ; int splitDP [ ] = new int [ numLen + 1 ] ; for ( int i = 0 ; i < numLen + 1 ; i ++ ) splitDP [ i ] = - 1 ; for ( int i = 1 ; i <= numLen ; i ++ ) { if ( i <= 9 && ( checkOdd ( number . substring ( 0 , i ) ) == 1 ) ) splitDP [ i ] = 1 ; if ( splitDP [ i ] != - 1 ) { for ( int j = 1 ; j <= 9 && i + j <= numLen ; j ++ ) { if ( checkOdd ( number . substring ( i , i + j ) ) == 1 ) { if ( splitDP [ i + j ] == - 1 ) splitDP [ i + j ] = 1 + splitDP [ i ] ; else splitDP [ i + j ] = Math . min ( splitDP [ i + j ] , 1 + splitDP [ i ] ) ; } } } } return splitDP [ numLen ] ; } public static void main ( String [ ] args ) { System . out . println ( splitIntoOdds ( "123456789123456789123" ) ) ; } }