Hi, I have been trying to solve this problem [Problem - 1102D - Codeforces] and I have been able to implement an O(n) solution which I am quite sure should be correct but shows a Time Limit Error(TLE) when the input size is 3*10^5 and the time limit is 2 seconds.
My solution is here Solution
Yeah, Thank you but I don’t think my solution is wrong,it works on all the test cases I have tried it on. I only want to understand why an O(n) solution will generate a TLE for an input size of 3*10^5 and a time limit of 2 seconds
Perhaps it’s the string concatenation? In many languages, string concatenation is actually O(n^2) instead of the more intuitive O(n).
Thank you very much,it turns out that string concatenation was the problem it was an O(n) operation and since I used it every time in my loop it became a total of O(n^2) and all this while I had always thought it was an O(1) operation!
Generally, when you are working with strings or array/vectors in general, you should always be careful using any predefined functions since their time complexity can be much higher than you thought.
