Anthony Watson
Anthony Watson

Reputation: 41

What's the most efficient way to calculate frequency of each letter in a string C++?

I was asked to do a task to count for each letter in the string how many times it occurs in it. It's assumed that all characters are alphabetical lower-case English letters. Also I should output string letters in ascending order, along with the frequency of each. I've tried to do so using std::set like the code below:

#include <iostream>
#include <set>
#include <string>

int main() {
    std::string s;
    std::cin >> s;
    int cnt[26] = {};

    for (int i = 0; i < s.length(); i++) {
        cnt[s[i] - 'a']++;
    }
    std::set <char> st;
    for (int i = 0; i < s.length(); i++) {
        st.insert(s[i]);
    }
    for (auto x : st) {
        std::cout << x << " : " << cnt[x - 'a'] << std::endl;
    }

    return 0;
}

Upvotes: 3

Views: 661

Answers (4)

Thakur Karthik
Thakur Karthik

Reputation: 3528

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
   return (a.second < b.second);
}
int main(){
   int len,cntS[26]={0},nonZero=0;
   string s;
   vector< pair<char,int> >v;
   cin>>s;
   len=s.length();
   for(int i=0;i<len;i++){
      cntS[s[i]-'a']++;
   }
   for(int i=0;i<26;i++){
      if(cntS[i]!=0){
        nonZero++;
        v.push_back(make_pair(char(i+'a'),cntS[i]));
      }
   }
   // Using sort() function to sort by 2nd element
  // of pair
  sort(v.begin(), v.end(), sortbysec);
  for(int i=0;i<v.size();i++){
      cout<<v[i].first<<v[i].second<<" ";
  }
  return 0;
}

enter image description here

Upvotes: 0

Temple
Temple

Reputation: 1631

You can use map to store key -> no occurances, then move that pairs to vector and sort, the code below:

std::vector<std::pair<char, int>> getSortedChars(std::string const& input) {
        std::map<char, int> m;
        std::vector<std::pair<char, int>> vp;
        for (char c : input) {
                ++m[c];
        }
        for (auto e : m) {
                vp.emplace_back(std::move(e));
        }
        std::sort(vp.begin(), vp.end(), [=](std::pair<char, int>& l, std::pair<char, int>& r) {
                return l.second < r.second;});
        return vp;
}

The returned vector will have sorted pairs, then you can just print them.

Upvotes: 0

Alexcei Shmakov
Alexcei Shmakov

Reputation: 2353

You can omit std::set and just write like so

int main() {
    std::string s;
    std::cin >> s;
    int cnt[26] = {};

    for (int i = 0; i < s.length(); i++) {
        cnt[s[i] - 'a']++;
    }
    for (int i = 0; i < 26; ++i) 
        if (cnt[i] > 0)
            std::cout << (char)('a' + i) << " : " << cnt[i] << std::endl;

    return 0;
}

Instead saving in the std::set, we check the presence of a character in the cnt and to output if a symbol was.
This option takes less memory.

Upvotes: 2

Damian
Damian

Reputation: 21

You could have used std::map, something like:

std::map<char, int> mymap;
for  (auto &c: s){
    mymap [c]++;
}

Upvotes: 2

Related Questions