ERROR: AddressSanitizer: negative-size-param: (size=-1)

Question

Sorry for this messy code, but I have a question.

I tried to solve a LeetCode's 844 task. Its given that

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

1st Example

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

2nd Example

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

My solution here:

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        vector<char> a;
        vector<char> b;
        int id = 0; 
        for(int i = 0; i < S.length(); i++){
            a.push_back(S[i]);
            id++;
            if(S[i]=='#'){
                a.erase(a.begin()+id-2);
                id--;
                a.erase(a.begin()+id-1);
                id--;
            }
            if(S[i+1]=='#'){
                a.erase(a.begin()+id-1);  
                id--;
                i+=2;
            } 
        }id = 0;
        for(int i = 0; i < T.length(); i++){  
            b.push_back(T[i]);
            id++;
            if(T[i]=='#'){
                b.erase(b.begin()+id-2);
                id--;
                b.erase(b.begin()+id-1);
                id--;
            }
            if(T[i+1]=='#'){
                b.erase(b.begin()+id-1);
                i+=2;
            }
        }
        bool x;
        if(a.size()==0) x = true;
        else{
            for(int i = 0; i < a.size(); i++){
                if(a[i]==b[i]) x = true;
                else x = false;
            }
        }return x;
    }
};
//Input: S = "ab##", T = "c#d#"

Runtime Error Message

=================================================================
==32==ERROR: AddressSanitizer: negative-size-param: (size=-1)
#8 0x7f585c70d82f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x602000000151 is located 0 bytes to the right of 1-byte region [0x602000000150,0x602000000151)
allocated by thread T0 here:
#5 0x7f585c70d82f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
==32==ABORTING

But it gives me such an error. I think that everything fine here with size. Where is my mistake?

Answer 1

You have several issues in your code

int id = 0; 

for (int i = 0; i < S.length(); i++){
    a.push_back(S[i]);
    id++;
    if (S[i]=='#'){
        a.erase(a.begin()+id-2);
        id--;
        a.erase(a.begin()+id-1);
        id--;
    }
    if(S[i+1]=='#'){
        a.erase(a.begin()+id-1);  
        id--;
        i+=2;
    } 
}

• You don't handle '#'as first character (or extra '#').
• S[i+1] is out of bound when i == S.size() - 1
• your i += 2 is done in addition to the regular ++i.

Your code can be simplified with:

std::string backspace_string_simplification(const std::string& s)
{
    std::string res;

    for (char c : s) {
        if (c != '#') {
            res.push_back(c);   
        } else if (!res.empty()) {
            res.pop_back();   
        }
    }
    return res;
}

Demo

Then, your "string comparison":

bool x;
if (a.size() == 0)
    x = true;
else {
    for(int i = 0; i < a.size(); i++) {
        if(a[i]==b[i]) x = true;
        else x = false;
    }
}
return x;

• when a is empty, string are equal if b is empty too.
• if size of a and b differs, you have either out of bound access in the loop, or ignore remaining comparison (whereas it should be false).
• your if in the loop is equivalent to x = (a[i] == b[i]), so your loop is equivalent to (with correct size) x = a.back() == b.back().

You can simply do return a == b; (either std::string and std::vector<char> handle that).

resulting in

bool backspaceCompare(string lhs, string rhs) {
    return backspace_string_simplification(lhs) == backspace_string_simplification(rhs);
}