Optimise a Python/ C++ algorithm

I was participating in a competitive programming contest, and faced a question where out of four test cases, my answer was correct in 3, but exceeded time limit in 4th.

I tried to get better results by converting my code from python to cpp (I know that time complexity remains same, but it was worth a shot 🙂)

Following is the question:

A string is said to be using strong language if it contains at least K consecutive characters ‘*’. You are given a string S with length N. Determine whether it uses strong language or not.

Input:

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains two space-separated integers N and K.
  • The second line contains a single string S with length N.

Output:

Print a single line containing the string “YES” if the string contains strong language or “NO” if it does not

My python approach:

for _ in range(int(input())):
    k = int(input().split()[1])
    s = input()
    s2 = "".join(["*"]*k)
    if len(s.split(s2))>1:
        print("YES")
    else:
        print("NO")

My converted Cpp code (converted it myself)

#include <iostream>
#include<string>

using namespace std;

int main() {
    // your code goes here
    int t;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        /* code */
        int n,k;
        std::cin >> n >> k;
        string str;
        cin >> str;
        string str2(k,'*');

        size_t found = str.find(str2);
        if (found != string::npos){
            std::cout << "YES" << std::endl;
        } else {
            std::cout << "NO" << std::endl;
        }
    }
    return 0;
}

Please guide me how can I reduce my time complexity?

Other approaches : “Using find() function instead of split or using for loop”

Edit: Sample Input :

2
5 1
abd
5 2
*i**j

Output :

NO
YES

Answer

The bounds you posted suggest that linear time is OK in Python. You can simply keep a running track of how many asterisks you have seen in a row.

T = int(input())
for _ in range(T):
    n, k = map(int, input())
    s = input()
    count, ans = 0, False
    for c in s:
        if c == "*":
            count += 1
        else:
            count = 0
        ans = ans or count >= k
    if ans:
        print("NO")
    else:
        print("YES")

I can also tell you why you are TLE’ing. Consider the case where n = 1e6, k = 5e5, and s is a string where the first k-1 characters are asterisks. The find method you have is going to check every position for matching the str2 you created. This will take O(n^2) time, giving you a TLE.