Table of Contents
Given a string, write a function that will find the second most frequent character
Example
INPUT :
s = “aabbbc”
OUTPUT :
‘a’ is the second most frequent character
Time Complexity : O(n)
Algorithm
1. Scan the input string and construct a character count array from input string
ie, In the above example,
count of a is 2, so count[‘a’] = 2
count of b is 3, so count[‘b’] = 3
count of c is 1, so count[‘c’] = 1
2. Now, find the second largest value in count array
C++ Program
#include <bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;
void secondFreqChar(string s)
{
int count[NO_OF_CHARS] = {};
for(int i=0; i<s.size(); i++)
{
count[s[i]]++; //increment the count of each character by using ASCII of character as key
}
//Finding the second largest number in count array
int first = 0, second =0;
for(int i=0; i < NO_OF_CHARS; i++)
{
//If the current char count is less than first, then change both variables
if(count[i] > count[first]) //
{
second = first;
first = i;
}
//If it is inbetween first and second
else if(count[i] > count[second] && count[i] != count[first])
{
second = i;
}
}
if (second != '\0')
{
cout<<"second most frequent character is "<<char(second)<<endl;
}
else//if there is no second frequent character
{
cout<<"there is no second most frequent character"<<endl;
}
}
int main()
{
string s = "tut";
cout<<"Input string is "<<s<<endl;
secondFreqChar(s);
}