1

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

  • 1
    how did you find out that `"B"` occurs most often in your example? Thats how you do it ;). Please show your code. No matter how broken or incomplete it helps us to help you. – 463035818_is_not_an_ai Jan 22 '21 at 16:52
  • 3
    Sorry, but SO is not a code-writing service. Did you try anything at all yet? What specific problem(s) did you encounter? – underscore_d Jan 22 '21 at 16:54
  • I just made a simple array as an example. –  Jan 22 '21 at 16:55
  • Among possible duplicates is [this question](https://stackoverflow.com/questions/15055800/element-with-highest-occurence-in-array-of-strings) – underscore_d Jan 22 '21 at 16:57
  • @Jithin D Mathew What is the type of elements of the array? That is show how the array is declared. Are elements of the type std::string or const char *? – Vlad from Moscow Jan 22 '21 at 16:57
  • You could try looking at some [search algorithms](https://en.wikipedia.org/wiki/Search_algorithm) to get some ideas. – TenderShortGoldenRetriever Jan 22 '21 at 17:41
  • Real easy. Use `std::map`. The `std::string` is the string you read. The `int` is the frequency. If the string (key) is found, increment the frequency (value). – Thomas Matthews Jan 22 '21 at 18:48

2 Answers2

0

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
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • Wow. You may want consider including an example that uses `std::map`, where *string* is the string read and *int* is the frequency. I believe it will be shorter than your first two examples. – Thomas Matthews Jan 22 '21 at 18:50
  • @ThomasMatthews There is at least one drawback of using this approach is that you will not get an iterator to the target element of the array. – Vlad from Moscow Jan 22 '21 at 18:56
0

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.

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154