Reversing the positions of words in a string without changing order of special characters in O(1) space limit

Question

During mock interview I come up with this question. Interviewer first ask this question without any space limitations. Then he continued with space-limited version. To be on the same page. In the question a string and container class consist of delimiters are given. This is up to you to decide suitable container class and the language of response. I think sample input and output would be enough to understand what really question is.

Input:

"Reverse#Strings Without%Changing-Delimiters"

Output:

"Delimiters#Changing Without%Strings-Reverse"

Note That: Position of "#", "%"," ","-" is not changed

I came up with the solution below:

string ChangeOrderWithoutSpecial(string s, unordered_set<char> delimiter)
{
    stack<string> words; // since last words outs first
    queue<char> limiter; // since first delimiter outs first
    string response =""; //return value
    int index=-1; // index of last delimiter visited
    int len=s.length();
    for (int i =0 ; i <len;i++)
    {
        if(delimiter.find(s[i]) != delimiter.end()) // i-th char is a delimiter character
        {
            string temp=s.substr(index+1,i-index-1);
            words.push(temp);
            char t =s.at(i);
            limiter.push(t);
            index=i;
        }
    // i realized that part after interview under assumption starting with word and no double delimiters ie, each word followed by one delimiter
    if(index!=s.length()-1)
    {
        string temp=s.substr(index+1,s.length()-index-1);//until the end;
        cout<<temp<<endl;
        words.push(temp);
    }
    while(!limiter.empty())
    {
        response+=words.top()+limiter.front();

        words.pop();
        limiter.pop();
    }
    response+=words.top();
    return response;  

} 

However I couldnt find a o(1) space solution ? Anyone know how ? I also could not figure out if there are multiple delimiters , that also be appricated. Thank you anyone spend time even reading.

Answer 1

Instead of rotating the string, it can be also solved by successive reversing the string.

• Reverse the whole string. This is O(n) operation. In your case the string becomes sretimileD-gnignahC%tuohtiW sgnirtS#esreveR.
• Find all words and reverse each of them. This is O(n) operation. String is now equal to Delimiters-Changing%Without Strings#Reverse.
• Reverse delimiters. This is O(n) operation. You'll get wanted result: Delimiters#Changing Without%Strings-Reverse.

Each of these operations can be done in place, so the total memory complexity is O(1) and time complexity is O(n).

It is worth noting that with this approach each character will be visited 4 times (first reverse, finding words, reverse word, reverse delimiter), so (in general case) it should be faster than Igor Tandetnik's answer where characters in the middle of the string are visited many times. However, in special case where each word has the same length, Igor's solution will be faster because the first rotate operation won't exists.

Edit:

Reverse delimiters can be done in O(n) without extra memory in the similar way as the standard reverse. Just iterate through delimiters instead of whole set of characters:

1. Iterate forward until you reach delimiter;
2. Reverse iterate until you reach delimiter from the back;
3. Swap the current delimiters;
4. Continue procedure until your iterators meet.

Here is procedure in C++ which will do this job

void reverseDelimiters(string& s, unordered_set<char>& delimiters)
{
    auto i = s.begin(); auto j = s.end() - 1; auto dend = delimiters.end();
    while (i < j) {
        while (i < j && delimiters.find(*i) == dend) i++;
        while (i < j && delimiters.find(*j) == dend) j--;
        if (i < j) swap(*i, *j), i++, j--;      
    }
}

Answer 2

Find the first word and the last word. Rotate the string by length(last_word)-length(first_word): this would put the middle part in the correct position. In the example, that'll produce

ersReverse#Strings Without%Changing-Delimit

Then rotate the first and last part of the string, skipping the middle, by length(first_word):

Delimiters#Strings Without%Changing-Reverse

Repeat this algorithm for the substring between the two outermost delimiters.

"Rotate by m" operation can be performed in O(1) space and O(n) time, where n is the length of the sequence being rotated.