Shuffle String.

Problem of the day - Shuffle String

Tag - Easy

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

At first glance, problem seems pretty short and simple. I just declared a new string and by iterating over the given indices array, I updated the values in the string to get the final output, as per the logic.

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string res = s;
        for(int i=0;i<indices.size();i++) {
            res[indices[i]] = s[i];
        }
        return res;
    }
};

A pretty easy solution with O(n) time and space. But the bad part is run time is 15ms (faster then only 18%). It's time to improve the solution.

I am not able re-call any other method to solve this. Umm, let's head over to leetcode discussion tab.

A really good solution with O(n) time and O(1) space helped me cracked this.

So, the solution is to update the string in-place. (similar logic to cyclic sorting).

So, the idea is to iterate over the indices array from start to end and for each element, keep on swapping it with the value index till we find the correct index value.

For example, we have [2,0,1] . Here, at index 0 we have 2. At index 2 we have 1. So, we update it in-place (the string s too along with this).

Now, array is [1,0,2]. Still at index 0, we don't have 0. So we update it again which makes it [0,1,2]. Rest of the elements are already at right place. Yay! we are done.

Code -

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        for(int i=0;i<indices.size();i++) {
            while(i != indices[i]) {
                swap(s[i], s[indices[i]]);
                swap(indices[i], indices[indices[i]]);
            }
            cout << s << endl;
        }
        return s;
    }
};

Perfect, now, no extra space. What a feeling. Sigh.

You might like previous editions of my coding diary -