C++ time limit exceeded when it doesn't even execute the function

Question

While I was solving a problem in LeetCode, I found something very strange.

I have this line which I assume gives me a time limit exceeded error:

s.erase(i-k, k);

when I comment(//) this line, it doesn't show me time exceed error, but the strange part was, it has never executed even when i didn't comment it.

below is the entire code. and Here is the problem link.

class Solution {
public:
    string removeDuplicates(string s, int k) {
        char prev = s[0];
        int cnt = 1;
        cnt = 1;

        for(int i = 1; i < s.size() + 1; i++){
            if(s[i] == prev){
                cnt++;
            } else {
                if(cnt == k){
                    // when input is "abcd" it never comes to this scope
                    // which is impossible to run erase function. 
                    s.erase(i-k, k);

                    i = 0;
                }
                
                if(i >= s.size()) break;
                
                cnt = 1;
                prev = s[i];
            }
        }
        
        return s;
    }
};

When Input is "abcd", it never even go to the if scope where 'erase' function is in. Although 'erase' function never run, it still affect on the time complexity, and I can't get the reason.

Does anyone can explain this? or is this just problem of LeetCode?

Answer 1

Many online contest servers report Time Exceeding when program encounters critical error (coding bug) and/or crashes.

For example error of reading out of bounds of array. Or dereferencing bad (junk) pointers.

Why Time Exceeded. Because with critical error program can hang up and/or crash. Meaning it also doesn't deliver result in time.

So I think you have to debug your program to find all coding errors, not spending your time optimizing algorithm.

Regarding this line s.erase(i-k, k); - it may crash/hang-up when i < k, then you have negative value, which is not allowed by .erase() method. When you get for example i - k equal to -1 then size_t type (type of first argument of erase) will overflow (wrap around) to value 18446744073709551615 which is defnitely out of bounds, and out of memory border, hence your program may crash and/or hang. Also erase crashes when there is too many chars deleted, i.e. for erase s.erase(a, b) you have to watch that a + b <= s.size(), it is not controlled by erase function.

See documentation of erase method, and don't put negative values as arguments to this method. Check that your algorithm never has negative value i.e. never i < k when calling s.erase(i-k, k);, also never i-k + k > s.size(). To make sure there is no program crash you may do following:

int start = std::min(std::max(0, i-k), int(s.size()));
int num = std::min(k, std::max(0, int(s.size()) - start));
s.erase(start, num);