{x}
blog image

Shuffle String

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:

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.

Solution Explanation

The problem asks to shuffle a string s according to the permutation given in the indices array. The character at index i in s should move to the index indices[i] in the shuffled string.

The solution uses a simple approach: create a new array (or string) of the same size as the input string, and then populate it according to the indices array. The character at index i in the input string s is placed at index indices[i] in the output array. Finally, the output array is converted back to a string.

Time Complexity Analysis

The solution iterates through the input string once to populate the output array. This gives a time complexity of O(N), where N is the length of the input string. The conversion from the array back to a string in most implementations (like Python's ''.join() or Java's String.valueOf()) also takes O(N) time. Therefore, the overall time complexity is O(N).

Space Complexity Analysis

The solution creates a new array (or string) of size N to store the shuffled string. This means the space complexity is O(N). In-place shuffling is not possible because we need to preserve the original string.

Code Explanation (Python)

The Python code efficiently implements this approach:

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        ans = [0] * len(s)  # Create an array of the same size as s, initialized with 0s.
        for i, c in enumerate(s):  # Iterate through s with index i and character c
            ans[indices[i]] = c  # Place character c at the index specified by indices[i]
        return ''.join(ans)  # Convert the array to a string

The code iterates through the input string s using enumerate to get both the index i and the character c. It then places the character c at the index indices[i] in the ans array. Finally, it joins the elements of the ans array to form a string, which is the shuffled string.

The other language implementations follow the same logic, only differing slightly in syntax. They all achieve the same O(N) time and space complexity.