Maximize cost of forming a set of words using given set of characters | Java program for the above approach ; Function to find the maximum cost of any valid set of words formed by using the given letters ; Stores frequency of characters ; Find the maximum cost ; Utility function to find maximum cost of generating any possible subsets of strings ; Base Case ; Stores the current cost ; Stores the cost of by the current word ; Create a copy of the letterCounts array ; Traverse the current word ; Store the current index & check if its frequency is 0 or not ; If true , then update wordScore to - 1 ; Otherwise , add the cost of the current index to wordScore ; Decrease its frequency ; If wordScore > 0 , then recursively call for next index ; Find the cost by not including current word ; Return the maximum score ; Driver Code ; Given arrays ; Function Call
import java . io . * ; class GFG { public static int maxScoreWords ( String [ ] words , char [ ] letters , int [ ] score ) { int [ ] letterCounts = new int [ 26 ] ; for ( char letter : letters ) letterCounts [ letter - ' a ' ] ++ ; return helper ( words , 0 , letterCounts , score ) ; } public static int helper ( String [ ] words , int start , int [ ] letterCounts , int [ ] score ) { if ( start == words . length ) return 0 ; int currScore = 0 ; int wordScore = 0 ; int [ ] nextCounts = letterCounts . clone ( ) ; for ( int i = 0 ; i < words [ start ] . length ( ) ; ++ i ) { int idx = words [ start ] . charAt ( i ) - ' a ' ; if ( nextCounts [ idx ] == 0 ) { wordScore = - 1 ; break ; } wordScore += score [ idx ] ; nextCounts [ idx ] -- ; } if ( wordScore > 0 ) currScore = helper ( words , start + 1 , nextCounts , score ) + wordScore ; currScore = Math . max ( currScore , helper ( words , start + 1 , letterCounts , score ) ) ; return currScore ; } public static void main ( String [ ] args ) { String words [ ] = { " dog " , " cat " , " dad " , " good " } ; char letters [ ] = { ' a ' , ' a ' , ' c ' , ' d ' , ' d ' , ' d ' , ' g ' , ' o ' , ' o ' } ; int score [ ] = { 1 , 0 , 9 , 5 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } ; System . out . println ( maxScoreWords ( words , letters , score ) ) ; } }