Code for BINSTRING has O(N) time complexity still showing TLE

help
,
1

can somebody tell why below code for problem BINSTRING from starters 27 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;
}
2

The reason for TLE is too many operations. You have used only one loop but inside the loop there is substr function which has O(N) time complexity. So you loop has O(N^2) time complexity.

Here’s a small explanation on how to solve the problem:

Let’s take a binary string 1001 as input.

Following are the binary string we get after doing the operation as said in question:
001 101 101 100

So we notice that when 1st zero is removed and when 2nd zero is removed we get the same binary string so for n sequence of same character we will get n same binary string which we should count as 1 because we need only distinct binary strings.

3

Oh it slipped out of my mind that substr function take a O(N) time