Question 6

September 10, 2020

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 = "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(n²).
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 C implementation of the approach.

Program to find second most frequent character in a string

Java

// C Program to Find second most frequent character in a String
 
#include <stdio.h>
#include <string.h>
 
int main()
{
  	char str[110],answer;
  	int i, length;
  	int max = -1;
  	
  	int frequency[256] = {0}; 
 
  	printf("\nEnter the String of characters:  ");
  	gets(str);
  	
  	length = strlen(str);
  	
  	for(i = 0; i < length; i++)
  	{
  		frequency[str[i]]++;
	}
  		
  	for(i = 0; i < length; i++)
  	{
		if(max < frequency[str[i]])
		{
			max = freq[str[i]];
			answer = str[i];
		}
	}
	printf("\nThe second most frequent character in a Given String is= %c ", answer);
	
  	return 0;
}

Output
Enter the String of characters: aabbbcde
The second most frequent character in a Given String is= a

Java

// Java Program to find the second most frequent character in a given string
import java.util.*;
public class Main
{
  static final int CHARS = 256;
  static char secondMostFreqChar(String str1)
  {
    int[] ch = new int[CHARS];
    for (int i = 0; i < str1.length (); i++)
        (ch[str1.charAt (i)])++;
    int ch_first = 0, ch_second = 0;
    for (int i = 0; i < CHARS; i++)
      {
	if (ch[i] > ch[ch_first])
	  {
	    ch_second = ch_first;
	    ch_first = i;
	  }
	else if (ch[i] > ch[ch_second] && ch[i] != ch[ch_first])
	    ch_second = i;
      }
    return (char) ch_second;
  }
  public static void main (String args[])
  {
      Scanner sc=new Scanner(System.in);
      System.out.println ("Enter a string: ");
      String str1=sc.next();
    System.out.println ("The given string is: " + str1);
    char res = secondMostFreqChar (str1);
    if (res != '\0')
      System.out.println ("The second most frequent character in the string is: " +res);
    else
      System.out.println ("No second most frequent character found in the string");
  }
}

Output
Enter a string: visit prepinsta
The given string is: visit prepinsta
The second most frequent character in the string is: p

16 comments on “Question 6”

Bandaruanilkumar
Anil#very simple python code
str=input()
l=list(str)
v=[]
for i in l:
v.append(l.count(i))
v=sorted(v)
v=[*set(v)]
for i in l:
if l.count(i)==v[-2]:
print(i)
break

0

Log in to Reply
Harsha
#simple python code
n=input()
d={}
k=[]
L=[]
for i in n:
k.append(i)
for i in k:
if i not in d:
d[i]=1
else:
d[i]+=1
for i in d.values():
L.append(i)
L.sort()
A=L[-2]
if max(L)==1:
print(“No Second most frequent character”)
else:
for i,j in d.items():
if j==A:
print(i)

1

Log in to Reply
Anonymous
#include
#include
#include

using namespace std;

void checkPangram(string str){

vector freq(26,0);
int n=str.length();
int val=0;

transform(str.begin(),str.end(),str.begin(), ::tolower);

for(int i=0;i<n;i++){
freq[str[i]-97]+=1;
}

val=max_element(freq.begin(),freq.end())-freq.begin();
freq[val]=0;
// val=*max_element(freq.begin(),freq.end());
val=max_element(freq.begin(),freq.end())-freq.begin();

cout<<"Second most frequent: "<<char(val+97);
};

int main()
{
string str;
getline(cin, str);

checkPangram(str);

return 0;
}

0

Log in to Reply