- Published on

# Shuffle String.

- Authors
- Name
- Pankaj Tanwar
- @the2ndfloorguy

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