Finding the most and second most repetition character in a single string

Question

I can find the most repetition char, but I can't find the second most repetition char

I don't understand the logic to find the 2nd most repeated char

void most_frequent_letter(string str, struct frequents result[])



    int len = str.length();

    int max = 0, i = 0, k = 0, Secmax = 0, m = 0;

for (i = 0 ; i <= len; ++i)
{
    if (str[i] >= 48 && str[i] <= 57)
    {
        result[0].count = 0;
        break;
    }
    if(str[i] >= 65 && str[i] <= 90)
    {
        str[i] += 32;

    }
    result[i].letter = str[i];
    result[i].count++;

    if (result[i].count > max && result[i].letter != ' ')
    {
        max = result[i].count;
        result[0].count = result[i].count;
        result[0].letter = str[i];

    }


}
cout << result[0].letter << endl;

Answer 1

The details behind struct frequents are not given but from the provided code I guess only letters (isalpha()) are considered.
Although the code in the question looks like C, it is tagged as C++ and uses std::string so I suggest here a C++ solution.

The suggested solution uses a vector with one counter per letter ('a' to 'z').
The first stage consists in counting every occurrence of a letter in the sentence (ignoring case).
Then finding the maximum element in this vector gives the most repeated letter.
After cancelling the corresponding counter, the next maximum element in this same vector gives the second most repeated letter.

#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>

std::vector<int> // letter counts
count_letters(const std::string &str)
{
  auto counts=std::vector<int>(1+'z'-'a');
  for(const auto &c: str)
  {
    if(std::isalpha(c))
    {
      ++counts[std::tolower(c)-'a'];
    }
  }
  return counts;
}

int
main()
{
  const auto txt=std::string{"Here is a sentence"};
  auto counts=count_letters(txt);
  const auto max_iter=std::max_element(cbegin(counts), cend(counts));
  const auto max_index=std::distance(cbegin(counts), max_iter);
  std::cout << "max: " << char('a'+max_index)
                       << " (" << counts[max_index] << ")\n";
  counts[max_index]=0; // cancel first max found
  const auto second_max_iter=std::max_element(cbegin(counts), cend(counts));
  const auto second_max_index=std::distance(cbegin(counts), second_max_iter);
  std::cout << "second max: " << char('a'+second_max_index)
                              << " (" << counts[second_max_index] << ")\n";
  return 0;
}

(hope that helps)

---

Edit: the same thing in C style without any library function (except printf() at the end), after the comment "but i have to do it without algorithm and cctype"

#include <stdio.h>

#define LETTER_COUNT (1+'z'-'a')

void
count_letters(const char *str,
              int *counts)
{
  for(int i=0; str[i]; ++i)
  {
    int c=str[i];
    if((c>='A')&&(c<='Z'))
    {
      c+='a'-'A';
    }
    if((c>='a')&&(c<='z'))
    {
      ++counts[c-'a'];
    }
  }
}

int // index of max count
find_max_index(const int *counts)
{
  int idx=0;
  for(int i=1; i<LETTER_COUNT; ++i)
  {
    if(counts[i]>counts[idx])
    {
      idx=i;
    }
  }
  return idx;
}

int
main(void)
{
  const char *txt="Here is a sentence";
  int counts[LETTER_COUNT]={0};
  count_letters(txt, counts);
  const int max_index=find_max_index(counts);
  printf("max: %c (%d)\n",
         'a'+max_index, counts[max_index]);
  counts[max_index]=0; // cancel first max found
  const int second_max_index=find_max_index(counts);
  printf("second max: %c (%d)\n",
         'a'+second_max_index, counts[second_max_index]);
  return 0;
}

Answer 2

Here is a slightly different twist on obtaining the top 2 most frequent characters in a string. Since a std::map is a sorted associative container sorted by key, see std::map, after the initial map is created listing the frequency of each character within a std::map <char, int>, you can simply turn the members around (i.e. <int, char> and add the results of the first map to a second map specifying a std::greater<int> sort (instead of the default std::less<Key> sort order).

For example:

void find_most_repeated (std::string str)
{
    std::map<char, int> mchars;
    std::map<int, char, std::greater<int>> mfreq;
    size_t nmostfreq = 0;

    for (const auto& c : str)           /* fill char/occurrence map */
        mchars[c]++;

    if (mchars.size() < 2) {            /* validate 2 unique chars in str */
        std::cerr << "error: str consists of a single character.\n";
        return;
    }

    for (const auto& pair : mchars)     /* fill sorted occurrence/char map */
        mfreq[pair.second] = pair.first;

    for (const auto& pair : mfreq) {    /* output 2 most frequent chars */
        std::cout << " " << pair.second;
        if (++nmostfreq == 2)
            break;
    }
    std::cout << '\n';
}

Adding a short example (shamelessly borrowing the example from @K.Krunk), you could do:

#include <iostream>
#include <string>
#include <map>

void find_most_repeated (std::string str)
{
    std::map<char, int> mchars;
    std::map<int, char, std::greater<int>> mfreq;
    size_t nmostfreq = 0;

    for (const auto& c : str)           /* fill char/occurrence map */
        mchars[c]++;

    if (mchars.size() < 2) {            /* validate 2 unique chars in str */
        std::cerr << "error: str consists of a single character.\n";
        return;
    }

    for (const auto& pair : mchars)     /* fill sorted occurrence/char map */
        mfreq[pair.second] = pair.first;

    for (const auto& pair : mfreq) {    /* output 2 most frequent chars */
        std::cout << " " << pair.second;
        if (++nmostfreq == 2)
            break;
    }
    std::cout << '\n';
}

int main (void)
{
    find_most_repeated (std::string ("asdaaaasssaaaaa"));
}

Example Output

Running the program would produce the first and next most frequent characters seen, e.g.

$ ./bin/chars_most_repeated
 a s

I'm sure there are probably a dozen more ways to approach it.

Answer 3

I think you can store a letter counter as a std::map<char, int> for example. Then you just have iterate over your string and if the counter already contains the current char, you increment it, else you add it and set the value to zero.

Then:

• Search for the highest count value: You'll get the most frequent letter.
• Erase the corresponding element in the map.
• Search again for the highest count value: You'll get the second most frequent letter.

---

The following example should be more explicit:

#include <map>
#include <algorithm>

bool compare(const std::pair<char, int> & a, const std::pair<char, int> & b)
{
    return (a.second < b.second);
}
bool most_frequent_letter(const std::string & str, std::pair<char, char> & results)
{
    if(str.length() >= 2)
    {
        std::map<char, int> counter;

        for(const char & c : str)
            ++counter[c];

        std::map<char, int>::const_iterator it_max = std::max_element(counter.cbegin(), counter.cend(), &compare);
        char c_max = it_max->first;

        counter.erase(it_max);

        it_max = std::max_element(counter.cbegin(), counter.cend(), &compare);
        char c_second = it_max->first;

        results = std::make_pair(c_max, c_second);
        return true;
    }
    else
        return false;
}

The function most_frequent_letter() receives the desired std::string and a reference to a std::pair<char, char> where to store the most and the second most frequent letters in the string.
It returns a boolean whose the value equals true whether the search could be performed or false otherwise.

You can get them back this way:

// Create a string
std::string test_string("Hello world");

// Find the two most frequent letters
std::pair <char, char> most_frequents;
bool success = most_frequent_letter(test_string, most_frequents);

// Get them
char most, second_most;
if(success)
{
    most = most_frequents.first;         // first --> most frequent
    second_most = most_frequents.second; // second --> second most frequent
}

I tested it and it worked successfully.

I tried to make this example as simpler as possible, I hope it will help.

Answer 4

This is an example that works fine, it could be optimized if you want to.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <iterator>

void find_most_repeated(std::string strData)
{
    std::map<char, int> mChars;

    for (int i = 0; i < strData.size(); i++)
        mChars[strData[i]] ++;

    std::vector<std::pair<char, int>> v{ std::make_move_iterator(begin(mChars)), std::make_move_iterator(end(mChars)) };

    std::sort(begin(v), end(v), 
        [](const std::pair<char, int>&  p1, const std::pair<char, int>&  p2) {return p1.second > p2.second; });

    std::cout << v[0].first << " " << v[1].first << std::endl;
}

int main()
{
    find_most_repeated(std::string("asdaaaasssaaaaa"));
}