Maximize cost of forming a set of words using given set of characters | 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 ; Given arrays ; Function Call
def maxScoreWords ( words , letters , score ) : NEW_LINE INDENT letterCounts = [ 0 ] * ( 26 ) NEW_LINE for letter in letters : NEW_LINE INDENT letterCounts [ ord ( letter ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT return helper ( words , 0 , letterCounts , score ) NEW_LINE DEDENT def helper ( words , start , letterCounts , score ) : NEW_LINE INDENT if ( start == len ( words ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT currScore = 0 NEW_LINE wordScore = 1 NEW_LINE nextCounts = letterCounts NEW_LINE for i in range ( len ( words [ start ] ) ) : NEW_LINE INDENT idx = ord ( words [ start ] [ i ] ) - ord ( ' a ' ) NEW_LINE if ( nextCounts [ idx ] == 0 ) : NEW_LINE INDENT wordScore = - 1 NEW_LINE break NEW_LINE DEDENT wordScore += score [ idx ] NEW_LINE nextCounts [ idx ] -= 1 NEW_LINE DEDENT if ( wordScore > 0 ) : NEW_LINE INDENT currScore = helper ( words , start + 1 , nextCounts , score ) + wordScore NEW_LINE DEDENT currScore = max ( currScore , helper ( words , start + 1 , letterCounts , score ) ) NEW_LINE return currScore NEW_LINE DEDENT words = [ " dog " , " cat " , " dad " , " good " ] NEW_LINE letters = [ ' a ' , ' a ' , ' c ' , ' d ' , ' d ' , ' d ' , ' g ' , ' o ' , ' o ' ] NEW_LINE 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 ] NEW_LINE print ( maxScoreWords ( words , letters , score ) ) NEW_LINE