Ninja is playing with his alphabet toys. He has all the 26 lowercase alphabets. His granny wanted him to learn some maths as well.
So, she added a cost with each of the alphabets, gave him a cost array and gave him an integer. Let us denote the integer by symbol target. She asks Ninja to find the greatest word (with or without meaning) under the following constraints:
- The cost array is 0 indexed and cost of using alphabet at index i is given by cost[i] (Note: ‘a’ is denoted by index 0, ‘b’ is denoted by index 1 and so on)
- The total expenditure of characters used must be equal to target.
You have to help Ninja to print the greatest word. If you are unable to form any word, under the given constraints, then print “0”.
Note: If two words are given to you, then the greater of the two will be the one which comes later in the dictionary. For example, “hi” is greater than “hello”.
1 <= target <= 10000
1 <= cost[i] <= 10000
Kindly help me with the approach