# 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() {
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
```

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.