Problem Statement: Count Grouped Binary Substrings

In my last Post i gave the question to help people to solve the question and commented the code and its explanation if ever needed. But then, i think some of us really need a good explanation which i couldnt provide .So i am improving , providing better explanation, photos of the test case,etc for the community to get it in a better way with all my efforts.

Do upvote if you think the work i did was worth and you like it.

I found this problem during my JPMorgan Chase OA. It’s a good example of a string + grouping based DSA problem that tests your pattern observation.

You are given a binary string s consisting of only '0' and '1'.

A binary substring is called grouped if: - All '0's come together followed by all '1's, or - All '1's come together followed by all '0's.

For example, "0011" or "1100" are grouped, but "0101" is not.

You need to count the number of such non-empty substrings where: - The number of consecutive '0's and '1's are equal, and - All '0's and '1's are grouped together (e.g. "01", "0011", "1100", "000111", etc.)

Input

A binary string s of length up to 10^5.

Output

An integer denoting the total number of valid grouped substrings.

Example

Input:

00110011

Output:

6

Explanation

The valid grouped substrings are: - "0011"(twice) - "01" (twice) - "1100" - "10"

Total = 6.

Spoiler Ahead :)

Detailed Explanation and code are shared below

!

Explanation:-

The code works as first: we group all the grouped 0's,1's, and then try to make pairs of them to get the number of strings, for example.

In 00110011

Let's say we would get nums as

2 2 2 2
i.e.2 '0',s 2 '1's 2 '0's 2 '1's so now i make the ans from this count as lets say the array of the count be nums.

So for two contiguous groups nums[0] and nums[1] i.e. 2 0's ans 2 1's can make atmost min(2,2)=2 i.e. two substrings which satisfy the condition i.e. 01 , 0011

for e.g. if we get something like 000011 so we can make min(4,2) =2 substrings 0011 01 .

Similarly, we can do it for all adjacent groups by making up to min(of the two adjacent)groups

I hope you would have understood the explanation plz upvote if you like and understand __

Code:-

// this is code

#include <bits/stdc++.h>
using namespace std;

void solve(){
  string s;
    cin>>s;
    int n=s.size();
    
    
    vector<int>nums;
    int i=0;
    
    while(i<n){
      i++;
      int cnt=1;
      while(i<n && i==0 || s[i]==s[i-1]){
        cnt++;
        i++;
      }
      nums.push_back(cnt);
    }
    
    
    int ans=0;
    for(int i=0;i<nums.size()-1;i++){
      ans+=min(nums[i],nums[i+1]);
    }
    
    cout<<ans<<"\n";
}

int main() 
{
  int t;
  cin>>t;
    for(int i=0;i<t;i++){
      solve();
    }
    return 0;
}