↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
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.↵
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------↵
↵
↵
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↵
```↵
↵
---↵
↵
↵
!↵
↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
↵
## Explanation↵
↵
The valid grouped substrings are:↵
- `"0011"`(twice)↵
- `"01"` (twice)↵
- `"1100"`↵
- `"10"` ↵
↵
Total = `6`.↵
↵
---↵
↵
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.↵
↵
*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;↵
}↵
~~~~~↵
↵
↵
