Checking if a character occurs at least N times in the string. Any solution in algorithms?

Question

This question is not hard in terms of getting solution, but I would like to know if any C++ function or algorithm is available to solve it.

I got this thought while going through this question Count character occurrences in a string in C++

So would like to know if we have any option other than writing a function from scratch to check if there is a specific number of occurrences of a character in the string. For example let us say:

std::string s = "a_b_c_d_e_f_g_h_i_j_k_l_m";

and we want to find if there are at least 2 '_' in the string. If we use std::count it will return the count of all '_'. std::count_if will also behave in similar way. I can write a code to loop through the string and break as soon as the count reaches 2, but I would like to know if we have some existing solution in C++ algorithms or functions.

Thought process here is, if we get a very long string as an input and criteria of doing something is based on whether there is at least n number of occurrences of a specific character, then it is a waste to traverse through the whole string.

Why not simply something along the lines of `std::map counts; for (auto c : the_string) { counts[c]++; }` ? — Jesper Juhl, Aug 13 '20 at 17:57
That's not OP's question, he wants to terminate the loop early to avoid using cpu cycles once whe knows it;s done — Makogan, Aug 13 '20 at 17:59
For only 2 elements, you could call find() twice, passing the found iterator into the second. Doesn't scale too nicely, but probably could be made to work with some template kungfu that is beyond me :) — Michael Dorgan, Aug 13 '20 at 17:59
@Makogan Fine; then check the count in the loop and `break;` if it's above the threshold. — Jesper Juhl, Aug 13 '20 at 18:00
@JesperJuhl yes thats 1 way.. but would like to know if anything in algorithm or c++ function — novice, Aug 13 '20 at 18:02
@novice It's *easy* to check yourself what is available in [](https://en.cppreference.com/w/cpp/algorithm). — Jesper Juhl, Aug 13 '20 at 18:06

Amir Kirsh · Answer 1 · 2020-08-13T18:56:50.833

std::find_if with a proper functor would do the job:

std::string s1 = "a_b_c_d_e_f_g_h_i_j_k_l_m";
int count = 0;
bool found =
    std::find_if(s1.begin(), s1.end(),
        [&count] (char c) {
           return c == '_' && ++count == 2;
        }) != s1.end();

Though, I would prefer to create a new function for that, let's call it find_if_n:

template<typename Iterator, typename Predicate>
Iterator find_if_n(Iterator begin, Iterator end, Predicate&& pred, int n) {
    return std::find_if(begin, end,
                          [&pred, &n] (const auto& v) {
                             return pred(v) && --n == 0;
                          });
}

With a simpler usage:

bool found = find_if_n(s1.begin(), s1.end(), [] (char c) {
                  return c == '_';
             }, 2) != s1.end();

score 3 · Accepted Answer · answered Aug 13 '20 at 18:24

You can use for example std::find_if. Here you are

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

int main() 
{
    std::string s = "a_b_c_d_e_f_g_h_i_j_k_l_m";
    
    std::string::size_type n = 0;
    
    auto it = std::find_if( std::begin( s ), std::end( s ),
                             [&n]( const auto &c )
                             {
                                 return c == '_' && ++n == 2;
                             } );
                   
    std::cout << std::distance( std::begin( s ), it ) << '\n';                 
                       
    return 0;
}

The program output is

That is the algorithm stops its execution as soon as it found the second character '_'.

thibsc · Answer 3 · 2020-08-13T18:28:02.607

A possible solution is to use std::all_of() because this function stops when the predicate is false:

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

int main()
{
    std::string str = "a_b_c_d_e_f_g_h_i_j_k_l_m";
    char search = '_';
    int count = 0, limit = 2;
    
    std::all_of(str.begin(), str.end(), [&search, &count, &limit](const char& c){
        std::cout << c << " ";
        if (c == search){
            count++;
        }
        return count < limit;
    });
    
    std::cout << "\nContains at least " 
    << limit << " " << "'" << search << "' ? " << count 
    << std::endl;
}

So you browse your string as long as your predicate is wrong.
In this case, you just checked 4 characters in place of the complete string: a _ b _

This novel approach can perhaps be made to run really fast if the `string` is really really (mean _really_) big by using a `std::atomic count;` and `std::all_of(std::execution::par, ...`. Since it doesn't have to return an iterator to the second match, it's allowed to return early. — Ted Lyngmo, Aug 13 '20 at 18:50

cigien · Answer 4 · 2020-08-13T20:50:17.193

With c++20, you can write the following function:

namespace sr = std::ranges;
namespace sv = std::ranges::views;

bool has_count_elements(auto&& range, int count, auto elem)
{
    auto match = [=] (auto c) { return c == elem; };

    auto matches = sv::filter(range, match) | sv::drop(count - 1);

    return not sr::empty(matches);
}

and use it like this:

int main() 
{
    std::string s = "a_b_c_d_e_f_g_h_i_j_k_l_m";
    std::cout << has_count_elements(s, 2, '_');   // prints 1
}

Since filter and view evaluate the ranges lazily, i.e. only as much as needed, the function will return after just count elements are found and the begin and end differ when evaluating sr::empty.

Also, you should constrain the function so that elem has the same type as the underlying type of range.

Here's a demo.

^{I'm sure I've seen this question, and this answer somewhere on SO, but I can't seem to find it.}

not much aware about c++20 is it possible to give little explanation how it works? — novice, Aug 14 '20 at 06:46

Checking if a character occurs at least N times in the string. Any solution in algorithms?

4 Answers4