Lexicographically largest string possible for a given cost of appending characters | Function to find the lexicographically largest string possible ; If sum is less than 0 ; If sum is equal to 0 ; If sum is less than 0 ; Add current character ; Check if selecting current character generates lexicographically largest string ; Backtrack if solution not found ; Find the lexicographically largest string excluding the current character ; Function to print the lexicographically largest string generated ; Function call ; Stores the string ; Print the lexicographically largest string formed ; Driver code ; Cost of adding each alphabet ; Cost of generating the string
def lexi_largest_string ( a , i , sum , v ) : NEW_LINE INDENT if ( sum < 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( sum == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( i < 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT v . append ( i ) NEW_LINE if ( lexi_largest_string ( a , i , sum - a [ i ] , v ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT v . pop ( - 1 ) NEW_LINE return lexi_largest_string ( a , i - 1 , sum , v ) NEW_LINE DEDENT def generateString ( a , sum ) : NEW_LINE INDENT v = [ ] NEW_LINE lexi_largest_string ( a , 25 , sum , v ) NEW_LINE s = " " NEW_LINE for j in range ( len ( v ) ) : NEW_LINE INDENT s += chr ( v [ j ] + ord ( ' a ' ) ) NEW_LINE DEDENT print ( s ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 1 , 1 , 2 , 33 , 4 , 6 , 9 , 7 , 36 , 32 , 58 , 32 , 28 , 904 , 22 , 255 , 47 , 69 , 558 , 544 , 21 , 36 , 48 , 85 , 48 , 58 ] NEW_LINE sum = 236 NEW_LINE generateString ( a , sum ) NEW_LINE DEDENT