Really curious how could this question be solved in O(n) time. O(nlogk) solution is not hard to be found, though...
Anybody figured out O(n) solution

You must use trie if you want to solve it in O(n) time.
Get some inspiration by looking at https://www.wikiwand.com/en/Trie