Find Second Most Repeated Word in a Sequence in C++

We are given an array of words, and we need to find the word whose frequency is the second largest in the array.

Let's assume some simple input and output scenarios

Let's assume we are having an array which consists of elements like ["point," "world," "articles," "articles," "articles," "world," "world," "world," "point"].

The frequency of words are ?

"point": 2
"world": 4
"articles": 3 // This will be the second most repeated word in the array.

So the second most repeated word is "articles," and our output is "articles."

Let's consider another scenario, Where there are group of similar words in an array, for example ["abc", "abc", "abc", "bab", "bab", "cat"]. The second most repeated word in sequence will be "bab".

"abc" = 3
"bab" = 2 // This will be the second most repeated word in the array.
"cat" = 1

We can hash and find the frequencies of each word in the given array of words and then return the second greater. In C++, we can use the unordered_map data structure.

Algorithm

The following are steps to be followed to perform the task

• Implement a hash table.

• The frequency of each string in the vector should be stored in hash table.

• Traverse the hash table after storing each string in hash table to find the string having second highest frequency.

• Then, print the string as output

Example

The C++ implementation to find the second most frequent word in a list is as follows ?

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
string solve(vector<string> words) {
   unordered_map<string, int> hash;
   for (auto word: words) {
      hash[word]++;
   }
   int first_max = INT32_MIN, sec_max = INT32_MIN;
   for (auto it: hash) {
      if (it.second > first_max) {
         sec_max = first_max;
         first_max = it.second;
      } else if (it.second > sec_max && it.second != first_max) {
         sec_max = it.second;
      }
   }
   for (auto it: hash) {
      if (it.second == sec_max) {
         return it.first;
      }
   }
   return "";
}
int main() {
   vector<string> words = { "point", "world", "articles", "articles", "articles", "world", "world", "world", "point" };
   cout << solve(words);
   return 0;
}

Output

"articles"

Conclusion

We can also use maps in C++, but it is useless as we don't want our words to be sorted lexicographically when hashed. Using the map will also be expensive as the insert operation takes O(log(n)) while in unordered_map, it takes O(1). For bigger input, though, we have to write our custom hash function to avoid conflicts and keep the time complexity O(1) only.