# PROBLEM LINK:

Setter: Satyam
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

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


2 Likes

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

signed main() {
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen(â€śinput2.txtâ€ť, â€śrâ€ť, stdin);
// for writing output to output.txt
freopen(â€ścontest.txtâ€ť, â€śwâ€ť, stdout);
#endif

ll t;
cin >> t;

while (t--) {

ll n;
cin >> n;

string s;
cin >> s;

unordered_set  <string> s2;

for (ll i = 0; i < s.size() ; i++) {
string s1 = s.substr(0, i) + s.substr(i + 1);

s2.insert(s1);
}

cout << s2.size() << "\n";
}

return 0;


}

why i am getting TLE in this code ??

10^5 * 10^5 > 10^9
Hence TLE

1 Like

you have solved a lot of problems congrats

Substring function itself takes O(n) and for each index using substring will take O(N^2) operation for a single String input.

okay

can somebody tell why below code is showing TLE
even when it has O(N) time complexity?

**APPROACH: **
I created every possible string that can be created by indexes and kept track of them using a map.since i am storing boolean values corresponding to each string,the size of map will give the number of distinct binary strings.

CODE

#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
string s;
cin >> s;
map<string,bool> mp;
string dummy;
ll ans=0;

for(ll i=0;i<s.length();i++)
{
if(i==0)
dummy=s.substr(1,s.length()+1);

else if(i==n)
dummy=s.substr(0,n);

else
dummy=s.substr(0,i)+s.substr(i+1,n+1);

mp[dummy]=true;
}

for(auto it:mp)
{
if(it.second==true)
ans++;
}
cout<<ans<<endl;
}
return 0;
}