# Shuffle String
**Difficulty:** EASY
[External](https://leetcode.com/problems/shuffle-string)
Canonical: https://scaleengineer.com/dsa/problems/shuffle-string
**Data structures:** Array, String
---
## Problem
You are 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:**

![](https://assets.glich.co/dsa/shuffle-string/image0.jpg) 

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

**Constraints:**

* `s.length == indices.length == n`
* `1 <= n <= 100`
* `s` consists of only lowercase English letters.
* `0 <= indices[i] < n`
* All values of `indices` are **unique**.

# Approaches
## In-place Shuffle with Cyclic Sort
This approach attempts to solve the problem without using extra space for the result, by shuffling the characters and indices in-place. It uses the concept of cyclic sort. We iterate through each position, and if the character at that position is not the one that should be there, we swap it with the character from its correct original position. To keep track of the movements, we also swap the corresponding indices. This process is repeated until every character is in its final correct position.
**Time:** O(n). Although there is a nested loop structure (`for` and `while`), each swap operation places at least one element in its correct final position. Since there are `n` elements, the total number of swaps across all iterations is at most `n-1`. Therefore, the total time complexity is linear. · **Space:** O(n). In Java, strings are immutable, so we must create a character array from the string, which takes `O(n)` space. If the input were a mutable character array, the space complexity would be `O(1)` as the shuffling is done in-place.
**Pros:** The algorithm is clever and demonstrates an in-place sorting technique.; Conceptually, it uses O(1) auxiliary space (ignoring the space for the mutable copy of the string).
**Cons:** More complex to understand and implement compared to the auxiliary array approach.; It modifies the input `indices` array, which might be an undesirable side effect.; In Java, it doesn't offer a space advantage over the simpler method due to string immutability.
### Explanation
The core idea is to place each character in its correct final position one by one. Since strings are immutable in Java, we first convert the input string `s` into a character array `charArray`.

We then iterate through the array from `i = 0` to `n-1`. For each index `i`, we check if the character at `charArray[i]` is already in its correct place. The correct place for the character originally at `s[i]` is `indices[i]`. We use the `indices` array to track where each character should go. If `indices[i]` is not equal to `i`, it means the character at `charArray[i]` needs to be moved.

We perform a cycle of swaps. We swap `charArray[i]` with `charArray[indices[i]]`. To ensure we don't lose track of the correct positions, we also swap `indices[i]` with `indices[indices[i]]`. This process continues in a `while` loop until `indices[i] == i`, which signifies that the correct character has been placed at index `i`.

After the outer loop finishes, all characters will be in their correct shuffled positions within `charArray`.

```java
class Solution {
    public String restoreString(String s, int[] indices) {
        char[] charArray = s.toCharArray();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            // While the character at index i is not in its correct place
            while (indices[i] != i) {
                int targetIndex = indices[i];

                // Swap the characters
                char tempChar = charArray[i];
                charArray[i] = charArray[targetIndex];
                charArray[targetIndex] = tempChar;

                // Swap the indices to reflect the character swap
                int tempIndex = indices[i];
                indices[i] = indices[targetIndex];
                indices[targetIndex] = tempIndex;
            }
        }

        return new String(charArray);
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `charArray`.
- Iterate from `i = 0` to `n-1`.
- Inside the loop, use a `while` loop that continues as long as `indices[i] != i`. This condition means the character currently at `charArray[i]` is not in its final correct position.
- Let `targetIndex = indices[i]`.
- Swap the character at `i` with the character at `targetIndex`.
- Swap the index at `i` with the index at `targetIndex`.
- This pair of swaps places one character into its correct final position and updates the `indices` array to reflect the new state. The `while` loop continues to resolve the new character that has been moved to position `i`.
- After the loops complete, the `charArray` is correctly ordered.
- Convert the `charArray` back to a string and return it.

## Using an Auxiliary Character Array
This is a straightforward and intuitive approach. We create a new character array to build the result. We iterate through the original string and the `indices` array. For each character at index `i` in the original string, we place it at the position `indices[i]` in our new array. This directly maps each character to its new shuffled position.
**Time:** O(n). We iterate through the string of length `n` once to place the characters. Creating the final string from the character array also takes `O(n)` time. · **Space:** O(n). We use an auxiliary character array of size `n` to store the result before converting it to a string.
**Pros:** Very simple and easy to understand and implement.; Highly efficient with a single pass over the data.; Does not modify the input arrays (`s` and `indices`).
**Cons:** Requires O(n) extra space, which is the main trade-off for its simplicity.
### Explanation
This method is the most direct way to solve the problem. The problem states that the character at the `i`-th position moves to `indices[i]` in the shuffled string. We can use this rule to build the new string.

First, we create an auxiliary character array, let's call it `resultChars`, with the same length as the input string `s`. This array will be used to construct the shuffled string.

Then, we iterate through the input string `s` and the `indices` array from `i = 0` to `n-1`. In each iteration, we take the character `s.charAt(i)` and its target destination `indices[i]`. We then place this character into our `resultChars` array at the target index. The assignment looks like this: `resultChars[indices[i]] = s.charAt(i)`.

After the loop has processed all the characters, `resultChars` will contain the fully shuffled sequence of characters. The final step is to convert this character array back into a string, which is our desired output.

```java
class Solution {
    public String restoreString(String s, int[] indices) {
        int n = s.length();
        char[] resultChars = new char[n];

        for (int i = 0; i < n; i++) {
            resultChars[indices[i]] = s.charAt(i);
        }

        return new String(resultChars);
    }
}
```
### Algorithm
- Let `n` be the length of the string `s`.
- Create a new character array `result` of size `n`.
- Loop for `i` from `0` to `n-1`:
-   The character `s.charAt(i)` should move to the position `indices[i]` in the shuffled string.
-   So, set `result[indices[i]] = s.charAt(i)`.
- After the loop, the `result` array contains all characters in their correct shuffled order.
- Convert the `result` array to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String restoreString(String s, int[] indices) {
    int n = s.length();
    char[] ans = new char[n];
    for (int i = 0; i < n; ++i) {
      ans[indices[i]] = s.charAt(i);
    }
    return String.valueOf(ans);
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {number[]} indices * @return {string} */ var restoreString =
  function (s, indices) {
    let rs = [];
    for (let i = 0; i < s.length; i++) {
      rs[indices[i]] = s[i];
    }
    return rs.join("");
  };

```

### CPP

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

```

### Python

```python
class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str: ans = [0] * len(s) for i, c in enumerate(s): ans[indices[i]] = c return '' . join(ans)

```