Count occurrences of a character in a string in C++

In this article, we will discuss different ways to count occurrences of a given character in a string in C++.

Table Of Contents

Method 1: Using std::count()

The first approach, that we will learn is the standard template library algorithm std::count() function. It accepts a range and a value as arguments. This range is the input iterators pointing to the starting and ending position of the string. The range used is [start, end), which contains all the elements between start and end, including the element pointed by start but not the element pointed by the end.

We can pass all characters of string as range and character ch as arguments to the count() function. If will check this character ch with each of the characters of the string over the range. So, the count() function returns a count i.e. the number of times the character ch matches with the characters in the given string over the range [start, end).

  • Time Complexity is of an order of n means linear. It is the range between first and last, comparing pairs of elements until a mismatch is identified. Time Complexity O(n).
  • Space Complexity is also of order 1 means constant. Space Complexity O(1).

Let’s see an example,

Advertisements
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str = "Hello World";
    char ch = 'l';

    // Get occurrence count given character in the string
    int cnt = count(begin(str), end(str), ch);

    cout << "Character " << ch << " occurs " << cnt << " times" << endl;

    return 0;
}

Output

Character l occurs 3 times

Method 2: Using std::count_if()

The second approach that we will learn is the standard template library algorithm std::count_if() function. The count_if() function accepts a range and a callback function (predicate) as arguments. It applies the given function to all elements of the range. This range is the input iterators pointing to the starting and ending position of the string. The range used is [start, end), which contains all the elements between start and end, including the element pointed by start but not the element pointed by the end. The count_if() function returns the number of elements in the range [start,end) for which predicate is true.

We can pass all characters of string as range and a function(predicate) as arguments to the count_if() function. The function (predicate) checks the character ch on each of the characters of the string over the range. So, the count_if() function counts the number of times the character ch matches with the characters of the given string over the range [start, end).

  • Time Complexity is of an order of n means linear. It is the range between first and last, comparing pairs of elements until a mismatch is identified. Time Complexity O(n).
  • Space Complexity is also of order 1 means constant. Space Complexity O(1).

Let’s see an example,

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str = "Hello World";
    char ch = 'l';

    // get occurrence count a character in string
    int cnt = count_if(
                    begin(str),
                    end(str),
                    [&ch](char c) {
                            return c == ch;
                    });

    cout << "Character " << ch << " occurs " << cnt << " times" << endl;

    return 0;
}

Output

Character l occurs 3 times

Method 3: Using std::find()

The third and last approach that we will learn is the standard template library algorithm std::find() function. The find() function accepts a range and value as arguments. This range is the input iterators pointing to the starting and ending position of the string. The range used is [start, end), which contains all the elements between start and end, including the element pointed by start but not the element pointed by the end. We can pass all characters of string as range and a character ch as arguments to the find() function. The find() function returns the iterator to the first occurrence of the specified character in the range [start, end) or string::npos, if the character is not found.

  • Time Complexity is of an order of n means linear. It is the range between first and last, comparing pairs of elements until a mismatch is identified. Time Complexity O(n).
  • Space Complexity is also of order 1 means constant. Space Complexity O(1).

Let’s see an example,

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string str = "Hello World";
    char ch = 'l';

   // Iterating from beginning of the string to end of the string

    int cnt = 0;
    for (int i = 0; (i = str.find(ch, i)) != std::string::npos; i++) 
    {
        cnt++;
    }

    cout << "Character " << ch << " occurs " << cnt << " times" << endl;
   return 0;
}

Output

Character l occurs 3 times

Summary

We have seen a detailed explanation of three approaches to count the occurrence of the character in the string. The first one is using the std::count() function, second is std::count_if() function, and the last is std::find() function. Also, we have seen the Time and Space Complexity of all three approaches.

Advertisements

Thanks for reading.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top