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;
}