Program to find second most frequent character

Given a string, find the second most frequent character in it. Expected time complexity is O(n) where n is the length of the input string.

Examples:

Input: str = "aabababa";
Output: Second most frequent character is 'b'

Input: str = "geeksforgeeks";
Output: Second most frequent character is 'g'

Input: str = "geeksquiz";
Output: Second most frequent character is 'g'
The output can also be any other character with 
count 1 like 'z', 'i'.

Input: str = "abcd";
Output: No Second most frequent character

A simple solution is to start from the first character, count its occurrences, then second character and so on. While counting these occurrence keep track of max and second max. Time complexity of this solution is O(n2).
We can solve this problem in O(n) time using a count array with size equal to 256 (Assuming characters are stored in ASCII format). Following is the implementation of the approach.

#include <bits/stdc++.h> using namespace std; #define NO_OF_CHARS 256     // CPP function to find the  // second most frequent character  // in a given string 'str'  char getSecondMostFreq(string str)  {      // count number of occurrences of every character.      int count[NO_OF_CHARS] = {0}, i;      for (i = 0; str[i]; i++)          (count[str[i]])++;         // Traverse through the count[] and     // find second highest element.      int first = 0, second = 0;      for (i = 0; i < NO_OF_CHARS; i++)      {          /* If current element is smaller          than first then update both          first and second */         if (count[i] > count[first])          {              second = first;              first = i;          }             /* If count[i] is in between first          and second then update second */         else if (count[i] > count[second] &&                  count[i] != count[first])              second = i;      }         return second;  }     // Driver code  int main()  {      string str = "geeksforgeeks";      char res = getSecondMostFreq(str);      if (res != '\0')          cout << "Second most frequent char is " << res;      else         cout << "No second most frequent character";      return 0;  }     // This code is contributed by rathbhupendra

Output:

Second most frequent char is g