1

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++

Ayushman Sinha
  • 75
  • 8
  • 1
    Insert at back, then use `std::reverse` to reverse it? – Some programmer dude Mar 22 '22 at 07:15
  • 3
    And please don't use such sites to learn programming, C++ or computer science, that's not what those sites are for. Invest in [some good C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and take computer-science classes. Once you're comfortable with multiple languages and all common data-structures and algorithms, you can use such sites as a kind of "programmers crossword puzzle". – Some programmer dude Mar 22 '22 at 07:17
  • 1. description + link to leetcode problem. 2. Show us your code. 3.get familiar with time complexity and `O` notation. 4. I doubt problem is what you are saying. – Marek R Mar 22 '22 at 07:28
  • 1
    do you want `add_char("abc",'d') == "dabc"` or `add_char("abc",'d') == "dcba"` ? – 463035818_is_not_an_ai Mar 22 '22 at 07:32
  • I want to add_char("abc",d) =="dcba" – Ayushman Sinha Mar 22 '22 at 07:37
  • And what is you later do `add_char("dcba", "e")` should the result be `"eabcd"`? – Some programmer dude Mar 22 '22 at 07:45
  • @AyushmanSinha -- Please do not use abbreviations such as MLE, TLE, etc. Spell out in English what these abbreviations are supposed to mean. Contrary to popular belief, most C++ programmers have never heard of these abbreviations, and do not go to these "competitive programming" websites where these abbreviations and acronyms exist. – PaulMcKenzie Mar 22 '22 at 07:55

1 Answers1

2

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.

huseyin tugrul buyukisik
  • 11,469
  • 4
  • 45
  • 97