# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Satyam

Tester: Abhinav Sharma, Aryan

Editorialist: Lavish Gupta

# DIFFICULTY:

Simple

# PREREQUISITES:

There are no such pre-requisites for the problem. You need to be comfortable with loops and conditional statements to solve this problem.

# PROBLEM:

You are given a binary string S of length N.

You have to perform the following operation **exactly** once:

- Select an index i (1 \le i \leq N) and delete S_i from S. The remaining parts of S are concatenated in the same order.

How many **distinct** binary strings of length N-1 can you get after applying this operation?

# QUICK EXPLANATION:

- Let str_i represents the string obtained after deleting the i^{th} character from the string. Compare str_i and str_{i+1}. When are they same? When are they different? What if we consider str_i and str_j?

# EXPLANATION:

Let us use the notations as defined in the Quick Explanation and try to answer the questions that are asked there.

Consider a continuous block of 0s. If we remove any 0 from this continuous block, then the resulting strings will be equal. The same holds for a continuous block of 1's. So, if S_i = S_{i+1}, then the resulting str_i will be equal to str_{i+1}.

This motivates us to consider the string as the blocks of 0s and 1s. Let us represent the string as S = O_1Z_1O_2Z_2...O_KZ_K, where Z_i represents a block of 0s and O_i represents a block of 1s. (It is possible that string starts with 0 or ends with 1, all these cases are equivalent, so the above representation is good enough for us).

We have seen that if we remove any 1 from O_i, the resulting strings will be equal. The only case to consider is, if we remove 1 from O_i in one case and from O_j in second case (i \neq j).

The first string will be: O_1Z_1...Z_{i-1}(O_i-1)Z_i...O_jZ_j...O_KZ_K

The second string will be: O_1Z_1...Z_{i-1}O_iZ_i...(O_j-1)Z_j...O_KZ_K

We can see that strings differ at the O_i block. So these both strings are different.

Therefore, total number of **distinct** strings that we can obtain is equal to the number of continuous blocks of 0s and 1s.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

## Editorialist's Solution

```
#include<bits/stdc++.h>
#define ll long long
using namespace std ;
int main()
{
ll t;
cin >> t ;
while(t--)
{
int n ;
string str ;
cin >> n >> str ;
int ans = 1 ;
for(int i = 1 ; i < n ; i++)
if(str[i] != str[i-1])
ans++ ;
cout << ans << '\n' ;
}
return 0;
}
```