how to find the maximum occurrence of a string in string array in c++

Question

I have a string array like

{"A", "B", "AA", "ABB", "B", "ABB", "B"}

how do I find the string ( "B" ) which occurs the largest number of times in an array like this in c++?

Thank you

Answer 1

If elements of the array has the type std::string then without using additional memory resources the function that finds the element that occurs more often in an array can look the following way as it is shown in the demonstrative program below.

#include <iostream>
#include <string>

size_t max_occurence( const std::string a[], size_t n )
{
    size_t max = 0;
    size_t max_count = 0;
    
    for ( size_t i = 0; i != n; i++ )
    {
        size_t j = 0;
        
        while ( j != i && a[j] != a[i] ) ++j;
        
        if ( j == i )
        {
            size_t count = 1;
            while ( ++j != n )
            {
                if ( a[j] == a[i] ) ++count;
            }
            
            if ( max_count < count )
            {
                max = i;
                max_count = count;
            }
        }
    }
    
    return max;
}

int main() 
{
    std::string a[] = { "A", "B", "AA", "ABB", "B", "ABB", "B" };
    
    auto max = max_occurence( a, sizeof( a ) / sizeof( *a ) );
    
    std::cout << "The most often encountered string is " << a[max] << '\n';

    return 0;
}

The program output is

The most often encountered string is B

An alternative approach is to write a generic template function. For example

#include <iostream>
#include <string>
#include <functional>
#include <iterator>

template <typename ForwardIterator, 
          typename BinaryPredicate = std::equal_to<typename std::iterator_traits<ForwardIterator>::value_type>>
ForwardIterator max_occurence( ForwardIterator first, 
                               ForwardIterator last, 
                               BinaryPredicate binary_predicate = BinaryPredicate() )
{
    auto max = first;
    typename std::iterator_traits<ForwardIterator>::difference_type max_count = 0;
    
    for ( auto current = first; current != last; ++current )
    {
        auto prev = first;
        
        while ( prev != current && !binary_predicate( *prev, *current ) ) ++prev;
        
        if ( prev == current )
        {
            typename std::iterator_traits<ForwardIterator>::difference_type count = 1;
            
            while ( ++prev != last )
            {
                if ( binary_predicate( *prev, *current ) ) ++count;
            }
            
            if ( max_count < count )
            {
                max = current;
                max_count = count;
            }
        }
    }
    
    return max;
}


int main() 
{
    std::string a[] = { "A", "B", "AA", "ABB", "B", "ABB", "B" };
    
    auto max = max_occurence( std::begin( a ), std::end( a ) );
    
    std::cout << "The most often encountered string is " << *max << '\n';

    return 0;
}

The program output is the same as shown above

The most often encountered string is B

Answer 2

Here's an example using std::map.

typedef std::map<std::string, int> Frequency_Map;
int main()
{
  const std::vector<std::string> test_data =
  {
      "A", "B", "AA", "ABB", "B", "ABB", "B",
  };

  Frequency_Map    frequency_table;
  std::string s;
  const size_t length = test_data.length();
  for (unsigned int i = 0; i < length; ++i)
  {
      Frequency_Map::iterator iter(frequency_table.find(test_data[i]);
      if (iter != frequency_table.end())
      {
          ++(iter->second);
      }
      else
      {
          frequency_table[test_data[i]] = 1;
      }
  }

  for (Frequency_Map::iterator iter = frequency_table.begin();
       iter != frequency_table.end();
       ++iter)
  {
      std::cout << iter->first << "    " << iter->second << "\n";
  }
  return 0;
}

The code above builds a frequency table using std::map and then outputs the strings and their frequencies. The above code can easily be modified to find the string that has the largest (maximum) frequency.