Why is the other solution 10 times efficient despite having the same algorithm and data structures?

user_6609678 0
Viewed 92

I found a piece of code over leetcode and I compared the same to my solution.

Problem link: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii

Leetcode solution: (16 ms & 10.2 MB)

string removeDuplicates1(string s, int k) {
  vector<pair<char, short>> st;
  string res;
  for (auto ch : s) {
    if (st.empty() || st.back().first != ch) st.push_back({ ch, 0 });
    if (++st.back().second == k) st.pop_back();
  }
  for (auto& p : st) res += string(p.second, p.first);
  return res;
}

My solution: (32 ms & 132.5 MB)

string removeDuplicates2(string str, int k) {
   if(k == 1)
        return "";
    vector<pair<char, short>> S;
    for(int i=0; i<str.size(); i++) {
        if(!S.empty() && S.back().first == str[i])
            S.back().second++;
        else 
            S.push_back({str[i], 1});
        if(S.back().second == k)
            S.pop_back();
    }
    
    string result = "";
    for(auto& i : S) {
        result = result + string(i.second, i.first);
    }
    return result;
}

Leetcode execution result: enter image description here

Why removeDuplicates1 is faster and memory efficient than removeDuplicates2?

data-structures stack algorithm c++
1 Answers

Expanding @Johannes Schaub's comment into an answer, the issue is likely with this bit right here:

for(auto& i : S) {
    result = result + string(i.second, i.first);
}

The expression inside the for loop says to do the following:

  1. Evaluate the right-hand side of the assignment statement. To do so, create a brand-new string formed by cloning result and appending string(i.second, i.first).
  2. Overwrite result with the new string formed this way.

In other words, every time you go through this loop, you're duplicating the entire string that you've created so far (which could potentially be huge), then appending a few more characters to it, then deleting your old string and replacing it with the new one. This uses a lot of memory and takes a lot of time.

On the other hand, consider the loop from the solution:

for (auto& p : st) {
    res += string(p.second, p.first);
}

This uses the += operator, which says "expand the existing string res by tacking string(p.second, p.first) onto the end of it." This doesn't involve making any copies*, and so it uses less memory and takes less time.

Generally speaking, avoid writing lhs = lhs + rhs when you can instead write lhs += rhs, as the former statement makes a copy while the latter does not.

* Internally, the string may need to resize its internal buffer to get more room to hold the new characters, so it may need to copy things over. However, the strategy used to do this overallocates space so that the total work spent copying is linear in the final size of the sequence.

user_5015570
Related