I've had problems with this one and was unable to solve it on my Algorithms 1 exam:
Input: -n words -k letters
Problem: For each letter print out the one word which starts with that letter and has the least number of appearances. If there are more than one, write the lexicographically smallest one. The printing of a word counts as an appearance.
Complexity: Time: O (nlogn + k) Space: O ( n + k )
This is the first algorithm I am unable to solve in given time complexity and it is driving me crazy.
Appreciate the help!
n=6 words: dog bark dog woof doggy doggy
k=2 letters and corresponding outputs: d - 2 is the least number of appearances of a word starting with d , dog and doggy - dog is the lexicographically smaller one so we print dog
if we say d again, since we printed out dog, that counts as another appearance so the only word appearing twice is doggy, and we print that one