Question 6

Program to find second most frequent character

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(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 C implementation of the approach. 

Program to find second most frequent character in a string

// 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 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

2 comments on “Question 6”


  • abhinay

    #python
    b=str(input(“input”))
    a=b.replace(” “,””)
    c={}
    for i in a:
    if i in c:
    c[i]+=1
    else:
    c[i]=1
    s=sorted(c.values())
    g=s[-2]
    print(list(c.keys())[list(c.values()).index(g)])


  • Mohd Saif

    #python
    def second_most_frequent_char(str):
    no_of_char=256
    count=[0]*no_of_char
    for i in range(len(str)):
    count[ord(str[i])]+=1
    first,second=0,0
    for i in range(no_of_char):
    if(count[i]>count[first]):
    second=first
    first=i
    elif(count[i]>count[second] and count[i]!=count[first]):
    second=i
    return chr(second)
    string=input()
    res=second_most_frequent_char(string)
    if(res!=’\0′):
    print(“second most frequent character is:”,res)
    else:
    print(‘no second most frequent char’)