Find, second, frequent, character

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);
}

Try It

 

Translate ยป