0

I need to replace the whitespaces " " in a string with @40 and have to do in O(1) space complexity. I cannot create a temp string or use auxiliary memory.

Input: Hello I love coding Coding Ninjas India

Output:Hello@40I@40love@40coding@40Coding@40Ninjas@40India

This is my current code:

#include<iostream>
using namespace std;
string replaceSpaces(string &str)
{
    int i=0;
    string temp="";
     while(i < str.length())
    {
        if(str[i] ==' ')
        {
           str.erase(i,1);
           str.insert(i,"@40");
        }
        i++;
    } 
    return str;
}  
int main()
{
   string s="Hello I love coding Coding Ninjas India";
   cout << "Ans--> " << replaceSpaces(s) << endl;
}

When I am not writing str.erase() and directly inserting @40 my code is not running, so I do not understand why we have to use str.erase(i,1) and string by 1 before inserting.

Hudson
  • 312
  • 2
  • 18
vivek shah
  • 1
  • 2
    if you don't erase the space it will be shifted to position `i+3` where you find it again, then again you prepend `"@40"` and shift the space by 3, and find it again 3 iterations later, and so on... you should use a debugger to see what happens – 463035818_is_not_an_ai Aug 23 '22 at 16:17
  • 2
    _"...in O(1) space complexity no temp string can be used..."_ `str.insert(i,"@40");` this will internally copy the string buffer as the code adds more characters than it removes. This copy can potentially happen multiple times so `O(1)` will not be achieved. – Richard Critten Aug 23 '22 at 16:19
  • 1
    _"no temp string can be used"_ Consider removing `string temp` then. – Drew Dormann Aug 23 '22 at 16:19
  • Does this answer your question? [Replacing even digits in string with given string](https://stackoverflow.com/questions/73343501/replacing-even-digits-in-string-with-given-string) – Özgür Murat Sağdıçoğlu Aug 23 '22 at 16:22
  • 1
    See also [`std::string::find()`](https://en.cppreference.com/w/cpp/string/basic_string/find) and [`std::string::replace()`](https://en.cppreference.com/w/cpp/string/basic_string/replace) – Thomas Matthews Aug 23 '22 at 16:23
  • 5
    Doing the described task in `O(1)` requires violating several fundamental rules of physics of our shared universe. This is not going to be easy. – Sam Varshavchik Aug 23 '22 at 16:29
  • 2
    The size of the output string may be 3x as large as the input string which makes it impossible to store the output string, using `O(1)` memory, even if you reuse the input string; the best you can do is to change the function signature to `std::string replaceSpaces(std::string)`, count the number of spaces, call `resize` on the string passed as param and iterate backwards replacing content.You could print the desired output using `O(1)` memory of course by simply iterating through the string char by char and printing the char or `"@40"`, depending on whether you encounter a space char or not. – fabian Aug 23 '22 at 17:39
  • 1
    This feels like a badly worded question either from a college/university class or some coding website. The only reasonable way: scan first, count the spaces. Perform **one** allocation with the extra spaces times two. Scan the string backwards pushing the existing characters forwards, replacing the spaces with `"@40"` – Jeffrey Aug 23 '22 at 18:22
  • Alternatively, just use `std::string::replace` and only care about performance/complexity when it gets to show in a profile. FTW. – Jeffrey Aug 23 '22 at 18:24

0 Answers0