Scale Engineer

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
ArrayString

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

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);    }}

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.

Solutions

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);  }}

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 →

Next problem