SSCRIPT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div-3 Contest

Author & Editorialist: Daanish Mahajan
Testers: Shubham Jain, Aryan Choudhary

DIFFICULTY:

Simple

PREREQUISITES:

Running Sum

PROBLEM:

Given a string S of length N and an integer K, tell whether there exists a substring of length K having each character as '*'.

EXPLANATION:

Subtask 1: We can manually check all the possible N - K + 1 substrings of length K in \mathcal{O}(K * (N - K)) per test case.

Subtask 2: Assume the string starts with x_1 consecutive characters from the set [a, z] followed by x_2 consecutive characters '*' followed by x_3 consecutive characters from the set [a, z] and so on. So answer = max(x_{2i}) where i >= 1.

The values of x_i can be calculated linearly by comparing the present character with the previous character and incrementing the counter if they are the same or pushing the value of the counter in the vector and setting it to one if not. But it requires \mathcal{O}(N) extra space.

To avoid using vector, increment the counter only when the present character is a '*', else keep the value of counter as 0 and take the maximum value of the counter at each iteration as the answer.

So the final time complexity is \mathcal{O}(N) per test case.

SOLUTIONS:

Setter's Solution 
                #include<bits/stdc++.h>

                using namespace std;
                  
                const int maxt = 10, maxl = 1e6;

                int main()
                {   
                    int t; cin >> t;
                    int tn = 0;
                    while(t--){
                        int n, k; cin >> n >> k; tn += n;
                        string s; cin >> s;
                        for(char c : s){
                            assert((c >= 'a' && c <= 'z') || c == '*');
                        }            
                        int maxv = 0, cnt = 0;
                        // for(int i = 0; i <= n - k && maxv < k; i++){
                        //     if(s[i] != '*')continue;
                        //     int cnt = 0;
                        //     for(int j = i; j <= i + k - 1; j++){
                        //         if(s[j] != '*')break;
                        //         cnt++;
                        //     }
                        //     maxv = max(maxv, cnt);
                        // }
                        for(char c : s){
                            if(c == '*')cnt++;
                            else{
                                maxv = max(maxv, cnt); cnt = 0;
                            }
                        }
                        maxv = max(maxv, cnt);
                        string ans = maxv >= k ? "YeS" : "No";
                        cout << ans << endl;
                    }
                    assert(tn <= maxl);
                }
Tester's Solution 
                #include<bits/stdc++.h>
                 
                using namespace std;
                 
                const long long int mod = 1000000007L;
                long long int T,n,i,j,k,in,cnt,l,r,u,v,x,y;
                long long int m;
                string s;

                int main(void) {
                    ios_base::sync_with_stdio(false);cin.tie(NULL);
                    cin >> T;
                    while(T--)
                    {
                        cin >> n >> k >> s;
                        long long int mx=0,cnt=0;
                        for(auto x:s)
                        {
                            assert(('a'<=x&&x<='z')||(x=='*'));
                            if(x=='*')
                                cnt++;
                            else
                                cnt=0;
                            mx=max(mx,cnt);
                        }
                        cout<<(mx>=k?"YeS":"nO")<<endl;
                    } 
                    return 0;
                }
2

why do i get wa using kmp
https://www.codechef.com/viewsolution/44462797

1 Like
3

#include
using namespace std;
//&& s.find(str) != -1
//static const size_type npos = -1;
int main() {
int t;
cin>>t;
string out[t];
for(int i = 0; i < t; i++){
int n, k;
cin>>n>>k;
char str[k];
for(int j = 0; j < k; j++){
str[j] = ‘*’;
}
string s;
cin>>s;
if(s.find(str) == string::npos){
out[i] = “NO”;
cout<<s.find(str)<<endl;
}
else{
out[i] = “YES”;
//cout<<s.find(str)<<endl;
}
}
for(int i = 0; i < t; i++){
cout<<out[i]<<endl;
}
return 0;
}

My code runs fine for one testcase but prints NO for multiple test cases. Please help

4

My code is running for one test case only. Can anyone spot what is wrong with this code?

#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–){

    long long n,k,i;
    long long count =0,maxcount = 0;
    cin>>n>>k;
    string a;
    cin>>a;
    for(i=0;i<n;i++){
        if(a[i]=='*')
            count++;
       else
       {
           
           maxcount = max(maxcount,count);
           count =0;
       }
        }
       if(maxcount>=k){
           cout<<"YES"<<endl;
       }
       else
        cout<<"NO"<<endl;
    
    
}
return 0;

}

5

I think sliding window is also be a good approach for this one in O(N)…

6

i also got partial correct answer this question 30/100 :frowning:

1 Like
7

your code wont work for : a***** or the asterics that are in the last
because it not enters into the else part by the end of the loop but the count remains 5 and maxcount remains 0
so write
maxcount = max(maxcount,count) after the loop once again.