[SOLVED] Fastest way to insert a character at the beginning of the string in C++?


So while solving problems on Leetcode I came across this problem. To generate a string normally, I could just use str.push_back(‘a’). But if I want to generate the string backwards I would use this same method and reverse the string at the end. Using str.insert() resulted in Time Limit Exceeded and str=’a’+str; would as expected result in Memory Limit Exceeded. Wanted to know if there was an easy way to insert a character at the beginning of the string in C++


You already answered your own question by saying reversing. Just use += operator to append and then reverse.

As another way, first push elements into a stack then pop them to fill string.

If it is still slow, then divide the output into small segments and pipeline the reversing + appending parts to hide latency using multiple threads. While one thread is reversing a segment, another thread can create another segment. Then you join all threads and join their output segments to make single array of chars to be converted to string. If each segment is size of L1 cache, then the reversing should be fast.

If you can’t use threads, then you can still do the reversing inside sse/avx registers, they have shuffle commands that can help you use the instruction level parallelism to hide the latency, unless they are slower than L1 access.

Answered By – huseyin tugrul buyukisik

Answer Checked By – Dawn Plyler (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *