BINSTRING - Editorial

editorial
, , ,
1

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

#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 ??

3

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

1 Like
4

you have solved a lot of problems congrats

5

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

6

okay

7

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