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”


  • guptaaastha825

    #include
    using namespace std;
    bool cmp(pair&a, pair&b){
    return a.second>b.second;
    }
    int main(){
    string s=”abcdd”;
    mapmp;
    for(int i=0;i<s.length();i++){
    mp[s[i]]++;
    }
    vector<pair>v;
    for(auto it:mp){
    v.push_back(it);
    }
    sort(v.begin(),v.end(),cmp);
    int val=v[0].second;
    for(int i=1;i<v.size();i++){
    if(v[i].second<val){
    cout<<v[i].first;
    break;
    }
    }
    }


  • 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


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


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

1 2