String concatenation time complexity S+=X and S = S+X

Question

I was solving one the free problem on leetcode and I got the TLE(Time Limit Exceeded) when I used st = st+b instead of st+=b. I though both operations are the same. Are they not. Please elaborate. If there is some other issue then also do mention in the answer.

st is initially an empty string and b is a char

Links to the pictures to be more clear :

Here you can see I used st+=b

Here I used st=st+b

string frequencySort(string s) {
    priority_queue<pair<int,char>> pq;
    unordered_map<char,int> m;
        for(int i = 0;i<s.size();i++)
            m[s[i]]++;
    for(auto x:m)
        pq.push(make_pair(x.second,x.first));
    string st = "";
    while(!pq.empty()){
        int x = pq.top().first;
        char b = pq.top().second;
        while(x--)
        st=st+b;
        
        pq.pop();
    }
    return st;
}

[There is a difference between += and + for c++ string concatentation](https://stackoverflow.com/a/30401747/7484918). The += operator utilizes true concatentation and will have better performance. The A = A+B method makes copies and is more expensive. — Frebreeze, Oct 07 '21 at 19:48
Does this answer your question? [Efficient string concatenation in C++](https://stackoverflow.com/questions/611263/efficient-string-concatenation-in-c) — Pranav Hosangadi, Oct 07 '21 at 19:51
They are not the same, but what kind of data is this code being run on? Usually you won't see a difference unless there is a *lot* of string manipulation going on. Unless the reason for the time-out error is that there is a huge amount of data, or the `while` loop executes thousands (maybe millions) of times, maybe the `+=` came very close to a timeout, and you still need to use a different approach. — PaulMcKenzie, Oct 07 '21 at 20:10
Also, these online competition coding sites have questions where (if you solve them in C++) rarely does doing a change like this makes that big of an affect if the basic algorithm or scheme being used is slow. I am going to wager that `+=` was approaching the time limit, but just missed it, while using `+` put you over the threshold. Also, these sites are not keen on specific quirks in the various languages such as the subtleties of `+=` over `+`. Usually their questions pass the time limit if the approach being used is one that they had in mind as the optimal one. — PaulMcKenzie, Oct 07 '21 at 20:19

score 0 · Answer 1 · answered Oct 07 '21 at 19:52

They are not the same. operator+= does not need to create a new object. In the best case the string has enough capacity and no reallocation has to happen. operator+ on the other hand returns a new string. For illustration consider a somewhat typical implemenation of operator+ vs operator+=:

#include <string>
#include <iostream>
    
struct my_string {
    std::string value;

    my_string& operator+=(const my_string& other) {
        value += other.value;
        return *this;
    }

    my_string operator+(const my_string& other) {
        my_string result{*this};
        return result+=other;
    }
};

int main() {
    my_string f{"foo"};
    my_string b{"bar"};
    std::cout << (f+b).value << "\n";
    std::cout << (f+=b).value;
}

String concatenation time complexity S+=X and S = S+X

1 Answers1