How to find the shortest sequence of asterisks separating two different letters in a string using STL algorithms?

Question

I have a line like this:

A*A**B***A**

I am interested in the sequence of asterisks that are between two different letters, in particular, I need to find the length of the shortest such sequence. For the above line, the answer is of course 2:A**B

I can easily solve this problem using the traditional loop I'm used to:

const string s = "A*A**B***A**";
string::size_type last_letter=-1, min_seq_len=s.size();
for(int i = 0; i < s.size(); i++) {
    if(last_letter == -1 || s[i] == '*' || s[i] == s[last_letter]) {
        if(s[i] != '*') {
            last_letter = i;
        }
    } else {
        min_seq_len = min(min_seq_len, i-last_letter-1);
        last_letter = i;
    }
}

However, is there a way to do this using the C ++ iterator algorithm library , etc.?

, , , , . , , ++, , ..

Answer 1

, , .

• - . std::min_element .

• - " + + " . -, std::find_if.

, STL- . :

auto letter_pairs = letter_pair_generator(s);
const auto min_seq_len = std::min_element(
    std::begin(letter_pairs), std::end(letter_pairs),
    [](const auto& x) { return x.asterisk_count(); });

letter_pair_generator - std::string, , . :

string s = "A*A**B***A**";
for(const auto& p : letter_pair_generator(s)) cout << p;

A * A ** B

**

A ** B *** A

***

---

, <algorithm>. . / .

Answer 2

, . , , std::regex , . , .

• std::string::find_first_not_of

  int best = s.size();
  int prev = -1;
  int next;
  
  while ((next = s.find_first_not_of("*", prev+1)) >= 0) {
      if (prev >= 0 && s[prev] != s[next]) {
          best = min(best, next - prev - 1);              
      }
      prev = next;
  }  
  

Runnable: https://ideone.com/xdhiQt

2. std::regex :

   regex r("(?=([^*][*]*[^*]))");
   
   int best = s.size();
   for (auto i = sregex_iterator(s.begin(), s.end(), r); i != sregex_iterator(); ++i) {
       int pos = i->position(1);
       int len = i->length(1); 
       if (s[pos] != s[pos + len -1]) {
           best = min(len-2, best);
       }
   }   
   

Runnable: https://ideone.com/2UdRGG

Answer 3

You can also use find_first_not_offor string.

size_t min(str.length()), prev(0), found(0);
while((found = str.find_first_not_of("*", prev)) != std::string::npos) {
  if (str[found] != str[prev] && found - prev < min) {
    min = found + 1 - prev;
  }
  prev = found + 1;
}

demo