Least count of words required to construct a target String | C ++ program of the above approach ; countMap [ ] [ ] to store count of characters ; 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 [ ] ; Recursizevely function call for ( pos + 1 ) ; Update charAvailable [ ] ; Update charAvailable [ ] ; Recursizeve Call ; Update charAvailable [ ] ; Function to find the minimum number of stickers ; Base Case ; Fill the countMap Array ; Recusizeve function call to get minimum number of stickers ; Driver Code ; Given Input ; Function Call ; Print the result
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > countMap ; int cnt = INT_MAX ; void count ( int curCnt , int pos , vector < int > charAvailable , string target , vector < string > stickers ) { if ( curCnt >= cnt ) return ; int m = stickers . size ( ) ; int n = target . size ( ) ; if ( pos == n ) { cnt = min ( cnt , curCnt ) ; return ; } char c = target [ 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 ] ; } } } } int minStickers ( vector < string > stickers , string target ) { if ( target == " " ) return -1 ; if ( target . size ( ) == 0 ) return 0 ; if ( stickers . size ( ) == 0 ) return -1 ; int m = stickers . size ( ) ; countMap . resize ( m , vector < int > ( 26 , 0 ) ) ; for ( int i = 0 ; i < stickers . size ( ) ; i ++ ) { string s = stickers [ i ] ; for ( char c : s ) { countMap [ i ] ++ ; } } vector < int > temp ( 26 ) ; count ( 0 , 0 , temp , target , stickers ) ; return cnt == INT_MAX ? -1 : cnt ; } int main ( ) { vector < string > str = { " with " , " example " , " science " } ; string target = " thehat " ; int Result = minStickers ( str , target ) ; cout << Result ; }