Find maximum occurring word in given set of strings

Given a huge set of strings with duplicate strings present, find the maximum occurring word in it. If two words have same count, return any one of them.

For example,

Input:  

keys = [“code”, “coder”, “coding”, “codable”, “codec”, “codecs”, “coded”,
“codeless”, “codec”, “codecs”, “codependence”, “codex”, “codify”,
“codependents”, “codes”, “code”, “coder”, “codesign”, “codec”,
“codeveloper”, “codrive”, “codec”, “codecs”, “codiscovered”]

Output:

Maximum occurring word is: codec
It’s count is: 4

 


 

The idea is to use Trie (Prefix Tree) to solve this problem. We start by inserting each key into the trie and store its count so far (along with the key itself) in the leaf nodes. After all nodes are inserted into the trie, we perform its pre-order traversal (depth first search) and find maximum frequency word by comparing the count present at leaf nodes. Note that we can also use a map to solve this problem.

 
C++ implementation –
 

Download   Run Code

Output:

Word : codec
Count: 4

 

Exercise:
1. Extend this solution to print all maximum occurring word (having same count).
2. Extend this solution to print first k maximum occurring word.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂