Least count of words required to construct a target String | Java program of the above approach ; countMap [ ] [ ] to store count of characters ; Function to find the minimum number of stickers ; Base Case ; Fill the countMap Array ; Recursive function call to get minimum number of stickers ; Function to get minimum number of stickers for a particular state ; If an optimal solution is already there , return ; If Target has been constructed update cnt and return ; Update charAvailable [ ] ; Recursively function call for ( pos + 1 ) ; Update charAvailable [ ] ; Update charAvailable [ ] ; Recursive Call ; Update charAvailable [ ] ; Driver Code ; Given Input ; Function Call ; Print the result
import java . io . * ; import java . util . * ; class Sol { int [ ] [ ] countMap ; int cnt = Integer . MAX_VALUE ; public int minStickers ( String [ ] stickers , String target ) { if ( target == null ) return - 1 ; if ( target . length ( ) == 0 ) return 0 ; if ( stickers == null stickers . length == 0 ) return - 1 ; int m = stickers . length ; countMap = new int [ m ] [ 26 ] ; for ( int i = 0 ; i < stickers . length ; i ++ ) { String s = stickers [ i ] ; for ( char c : s . toCharArray ( ) ) { countMap [ i ] ++ ; } } count ( 0 , 0 , new int [ 26 ] , target , stickers ) ; return cnt == Integer . MAX_VALUE ? - 1 : cnt ; } private void count ( int curCnt , int pos , int [ ] charAvailable , String target , String [ ] stickers ) { if ( curCnt >= cnt ) return ; int m = stickers . length ; int n = target . length ( ) ; if ( pos == n ) { cnt = Math . min ( cnt , curCnt ) ; return ; } char c = target . charAt ( pos ) ; if ( charAvailable > 0 ) { charAvailable -- ; count ( curCnt , pos + 1 , charAvailable , target , stickers ) ; charAvailable ++ ; } else { for ( int i = 0 ; i < m ; i ++ ) { if ( countMap [ i ] == 0 ) continue ; for ( int j = 0 ; j < 26 ; j ++ ) { charAvailable [ j ] += countMap [ i ] [ j ] ; } count ( curCnt + 1 , pos , charAvailable , target , stickers ) ; for ( int j = 0 ; j < 26 ; j ++ ) { charAvailable [ j ] -= countMap [ i ] [ j ] ; } } } } } class GFG { public static void main ( String [ ] args ) { Sol st = new Sol ( ) ; String [ ] str = { " with " , " example " , " science " } ; String target = " thehat " ; int Result = st . minStickers ( str , target ) ; System . out . println ( Result ) ; } }