problem: QFUN from CEFT2020

submission link:

https://www.codechef.com/viewsolution/37207555

I am getting tle on my solution can someone suggest a faster one.

problem: QFUN from CEFT2020

submission link:

https://www.codechef.com/viewsolution/37207555

I am getting tle on my solution can someone suggest a faster one.

Since you are interested to know why your solution ran out of time, I’m gonna pick up a few costly operations that I can find in your code at glance.

.copy() takes O(N) time but is irrelevant in this context. But you should know that it’s heavy.

The real damage is caused by the pop(0) operation in the two nested while loops.

In python, the pop() operation takes constant time but popping any arbitrary position will cost O(N) as the list is restructured thereafter.

As for the problem, the hint is that if you choose any position of 0 and any position of 1 then the substring in between those positions included will be a valid substring.

Try to find out the answer in O(N) time.