Question 6

September 10, 2020

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

17 comments on “Question 6”


  • Nageswar

    a = input()
    b = dict()
    c = []
    for i in a:
    b[i] = 0
    for i in b:
    x = a.count(i)
    b[i] = x
    if x not in c:
    c.append(x)
    c.sort(reverse=True)
    if len(c) == 1:
    exit(print(“No Second most frequent character”))
    for i in b:
    if b[i] == c[1]:
    print(“Second most frequent character is”, i)


  • jasvinder

    #python
    from collections import Counter
    string = input()
    counter_string = Counter(string)
    max_two = counter_string.most_common(2)
    if max_two[1][1] <= 1:
    print("No Second most frequent character")
    else:
    print(max_two[1][0], max_two[1][1])


  • av.p

    // C Program to Find second most frequent character in a String

    #include
    #include

    int main()
    {
    char s[1000];
    int max=-1,smax=-1,i,freq[1000]={0};
    scanf(“%s”,s);

    for(i=0;i<strlen(s);i++){

    freq[s[i]]=freq[s[i]]+1;

    }

    for(i=0;imax){
    smax=max;
    max=i;
    }

    else if(freq[s[i]] > freq[s[smax]] && freq[s[i]] != freq[s[max]])
    smax = i;

    }

    printf(“%c-%d\n”,s[smax],freq[s[smax]]);
    printf(“%d-%d\n”,max,smax);

    return 0;
    }


  • afradbasha456

    JAVA:(first most and second most):

    import java.util.*;
    public class Main
    {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine(); //”grass is greener on the other side”
    int[] freq = new int[str.length()];
    char minChar = str.charAt(0), maxChar = str.charAt(0);
    int i, j, min, max;
    char minChar1 = str.charAt(0), maxChar1 = str.charAt(0);
    int min1,max1;

    //Converts given string into character array
    char string[] = str.toCharArray();
    for(int k = 0; k < string.length; k++){
    System.out.print(string[k]+" ");
    }

    //Count each word in given string and store in array freq
    for(i = 0; i < string.length; i++) {
    freq[i] = 1;
    for(j = i+1; j < string.length; j++) {
    if(string[i] == string[j] && string[i] != ' ' && string[i] != '0') {
    freq[i]++;

    //Set string[j] to 0 to avoid printing visited character
    string[j] = '0';
    }
    }
    }
    System.out.print("\n");
    for(int l = 0; l < string.length; l++){
    System.out.print(string[l]+" ");
    }
    System.out.print("\n");
    for(int m = 0; m < string.length; m++){
    System.out.print(freq[m]+" ");
    }
    System.out.print("\n");

    //Determine minimum and maximum occurring characters
    min = max = freq[0];
    for(i = 0; i freq[i] && string[i] != ‘0’) {
    min = freq[i];
    minChar = string[i];
    }
    //If max is less than frequency of a character
    //then, store frequency in max and corresponding character in maxChar
    if(max < freq[i]) {
    max = freq[i];
    maxChar = string[i];
    }
    }
    System.out.println(min);
    System.out.println(max);

    min1 = max1 = freq[0];
    for(int z = 0; z freq[z] && string[z] != ‘0’ && freq[z] != min ) {
    min1 = freq[z];
    minChar1 = string[z];
    }
    //If max is less than frequency of a character
    //then, store frequency in max and corresponding character in maxChar
    if(max1 < freq[z] && freq[z] != max ) {
    max1 = freq[z];
    maxChar1 = string[z];
    }
    }
    System.out.println(min1);
    System.out.println(max1);

    System.out.println("Minimum occurring character: " + minChar);
    System.out.println("Maximum occurring character: " + maxChar);
    System.out.println("2nd most Minimum occurring character: " + minChar1);
    System.out.println("2nd most Maximum occurring character: " + maxChar1);
    }
    }


  • somarapu

    #include
    #include
    #include
    using namespace std;

    int main()
    {
    string s; int val = 0, max, sec, a[26] = {0}, b[26] = {0};
    cin >> s;
    sort(s.begin(), s.end());
    for(auto i:s)
    {
    val = (int)tolower(i) – 97;
    a[val]++;
    b[val]++;
    }
    sort(a, a+26);
    max = a[25];
    int val1 = 1, i = 24;
    while (val1 == 1)
    {
    if(max != a[i])
    {
    sec = a[i];
    val1 = 0;
    }
    i–;
    }
    int pos = 0;
    for(int i =0; i < 26; i++)
    {
    if ( b[i] == sec )
    {
    pos = i + 97 ;
    break;
    }
    }
    cout <<"\n ans is " << (char)pos ;
    return 0;
    }


  • Gourav

    str = “aabababaccdddeffffff”

    dict={}
    for ele in str:
    if(ele in dict.keys()):
    dict[ele]+=1
    else:
    dict[ele]=1
    print(dict)

    l=list(dict.values())
    for j in range (2):
    for i in range (len(l)-1):
    if(l[i]>l[i+1]):
    l[i],l[i+1]=l[i+1],l[i]

    c=l[::-1][1]
    if(c!=1):
    print(c)
    else:
    print(‘Not Possible’)


  • Pal

    int main()
    {
    string s ;
    int ans = 0;
    int poi =0;
    getline(cin,s);
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    int freq[26] = {0};
    for(int i =0 ;i<s.length();i++)
    {
    freq[s[i] – 'a']++;
    }
    for(int i =0 ;i<26;i++)
    {
    if(ans<freq[i])
    {
    ans = freq[i];
    poi = i;

    }
    }
    freq[poi] = freq[poi] – ans;
    ans =0;
    for(int i =0 ;i<26;i++)
    {
    if(ans<freq[i])
    {
    ans = freq[i];
    poi = i;

    }
    }
    char chara = poi + 'a';
    cout<<"The second most frequent character in a Given String is "<<chara;

    return 0;
    }


  • Swapnil

    n = input(“enter : “)
    s = {i for i in n}
    m = {}
    for i in s:
    m.update({i:n.count(i)})
    a = m.pop(max(m))
    b = max(m)
    if a >= 2:
    print(“No”)
    else:
    print(b)


  • Arjunkumar

    Python Solution

    a=’aabababa’
    b=list(a)
    c=sorted(set(b),key=b.count,reverse=True)
    print(c[1])


  • Subhasis

    #include
    #include
    #include
    using namespace std;

    bool sortByVal(pair p,pair q)
    {
    return p.second > q.second;
    }

    char secondMostFrequent(string s)
    {
    unordered_map map;
    for(char c : s)
    {
    if(map.find(c) == map.end())
    map[c] = 1;
    else
    map[c] +=1;
    }

    vector<pair> freqs;
    for(auto kv : map)
    freqs.push_back(kv);

    sort(freqs.begin(),freqs.end(),sortByVal);

    return freqs[1].first;
    }

    int main() {
    string s;
    cin >> s;

    char output = secondMostFrequent(s);
    cout << output << endl;

    return 0;
    }


  • 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)])


    • Archibrata

      #Using Counter
      from collections import Counter
      s = ‘aababc’
      a = Counter(s)
      g = sorted(a.values())[-2]
      print(list(a.keys())[list(a.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’)

1 2