Shuffle String

Easy

#1408Time: 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.

Data structures

Array String

Prompt

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 i^th position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

indices

Example 2:

indices

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public String restoreString(String s, int[] indices) {3        char[] charArray = s.toCharArray();4        int n = s.length();5 6        for (int i = 0; i < n; i++) {7            // While the character at index i is not in its correct place8            while (indices[i] != i) {9                int targetIndex = indices[i];10 11                // Swap the characters12                char tempChar = charArray[i];13                charArray[i] = charArray[targetIndex];14                charArray[targetIndex] = tempChar;15 16                // Swap the indices to reflect the character swap17                int tempIndex = indices[i];18                indices[i] = indices[targetIndex];19                indices[targetIndex] = tempIndex;20            }21        }22 23        return new String(charArray);24    }25}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public String restoreString(String s, int[] indices) {3        int n = s.length();4        char[] resultChars = new char[n];5 6        for (int i = 0; i < n; i++) {7            resultChars[indices[i]] = s.charAt(i);8        }9 10        return new String(resultChars);11    }12}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String restoreString(String s, int[] indices) {4    int n = s.length();5    char[] ans = new char[n];6    for (int i = 0; i < n; ++i) {7      ans[indices[i]] = s.charAt(i);8    }9    return String.valueOf(ans);10  }11}

1/** * @param {string} s * @param {number[]} indices * @return {string} */ var restoreString =2  function (s, indices) {3    let rs = [];4    for (let i = 0; i < s.length; i++) {5      rs[indices[i]] = s[i];6    }7    return rs.join("");8  };

1class Solution {2public:3  string restoreString(string s, vector<int> &indices) {4    int n = s.size();5    string ans(n, 0);6    for (int i = 0; i < n; ++i) {7      ans[indices[i]] = s[i];8    }9    return ans;10  }11};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem