## Shilei Tian

PhD Student at Stony Brook University

## Question

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.

#### Example 1:

```
Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.
```

#### Example 2:

```
Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.
```

#### Example 3:

```
Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"
```

#### Example 4:

```
Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"
```

#### Example 5:

```
Input: s = "art", indices = [1,0,2]
Output: "rat"
```

#### Constraints:

`s.length == indices.length == n`

`1 <= n <= 100`

`s`

contains only lower-case English letters.`0 <= indices[i] < n`

- All values of indices are unique (i.e. indices is a permutation of the integers
from
`0`

to`n - 1`

).

## Idea

#### First Thought

I can come up with a simple solution immediately, that is to create a new string with same length as original one, and then map all characters from original string based on the indices.

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

The execution time is 16ms (73.18%), and memory usage is 15.5MB (30.16%). To be
honest, it is not a bad solution in terms of the execution time. However, the
memory usage is a little poor. We’re using non-in-place algorithm here, and fairly
speaking, that is the least memory usage for a non-in-place solution. If we want
to improve the memory usage, we must use an inplace solution, epecially when the
first argument of the function is a copy of original string `s`

.

#### In-Place Solution

An in-place solution must guarantee that when we map an element to a new place, the element at the new place must be mapped right next; otherwise, we will lose the element.

Let’s take a look at the first example. When we process the first element `c`

, it
should be mapped to the `4`

th slot. Therefore, we replace the `4`

th element `l`

with `c`

. Now we need to process the `l`

immediately, so it should go to the first
slot, and we replace the first element with `l`

. But what now? We’re back to the
start point. Are we going to do it again? Of course not, because we would be stuck
in an infinite loop. We need somehow to tell we’ve already processed a specific
element.

Here is the trick. When mapping an element to its new place, instead of just replace
the element at new place, we swap them. Then the element at new place goes to the
old place. Recall that elements in `indices`

represent that the `i`

th element should
be mapped to `indices[i]`

th slot. After the swap, the `indices[i]`

th element is
swapped to `i`

th slot. If we also swap `i`

th and `indices[i]`

th element in `indices`

,
we can keep this relation unchanged. Let’s still use the first example. After the
swap, `s`

becomes `lodeceet`

, and `indices`

becomes `[0,5,6,7,4,2,1,3]`

. Now if
we look at the `indices`

, basically it says the first element goes to the first
slot, which means we have already reach an end here. Everytime we do a swap, the
starting point reaches to its final position, which means `i == indices[i]`

. Therefore,
we can take `i == indices[i]`

as a condition to stop. That’s the essence of cyclic
sort, that is everytime we find a right position for a specific element.

## Solution

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

Runtime: 12 ms, faster than 91.66% of C++ online submissions for Shuffle String. Memory Usage: 15.2 MB, less than 93.44% of C++ online submissions for Shuffle String.