Domain 1EasyCORE

Shuffle String

The problem requires us to shuffle a given string `s` based on an array of indices. Each character in the string `s` needs to be moved to a new position specified by the corresponding value in the `indices` array. The goal is to return the shuffled string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Sort

1528. Shuffle String

Model: qwen2.5-coder:14b
Topics: Sort
FAANG asked: 1
Acceptance rate: 85.7%


Problem Breakdown

The problem requires us to shuffle a given string s based on an array of indices. Each character in the string s needs to be moved to a new position specified by the corresponding value in the indices array. The goal is to return the shuffled string.

Inputs:

  • A string s containing only lowercase English letters.
  • An integer array indices where each element indicates the new position of the character from the same index in s.

Outputs:

  • A new string that represents the shuffled version of s.

Implicit Constraints or Tricky Edge Cases:

  • The length of s is equal to the length of indices.
  • All values in indices are unique and form a permutation of integers from 0 to n-1.
  • The string s can be empty, but since the problem specifies 1 <= n <= 100, this edge case doesn’t apply here.

Intuition

A brute-force approach would involve creating a new string and iterating through each character in s, placing it at its corresponding position as specified by indices. This approach is straightforward but not optimal in terms of space complexity, as we create an additional string to store the result.

The key insight is that since indices is a permutation of integers from 0 to n-1, we can directly map each character to its new position without needing extra storage for intermediate results. This leads us to a more efficient approach using a list to build the shuffled string in place.

Approach

  1. Initialize an empty list result of the same length as s.
  2. Iterate through each character in s and its corresponding index.
  3. Place each character at the position specified by indices[i] in the result list.
  4. Join the list into a string and return it.

This approach ensures that we only use additional space for the result list, making it more efficient than creating multiple intermediate strings.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string s. We iterate through each character once.
  • Space Complexity: O(n), as we create a new list to store the shuffled characters.

Solution

def restoreString(s: str, indices: List[int]) -> str:
    # Initialize an empty list to hold the shuffled characters
    result = [''] * len(s)
    
    # Iterate through each character and its corresponding index
    for i in range(len(s)):
        # Place the character at the correct position specified by indices[i]
        result[indices[i]] = s[i]
    
    # Join the list into a string and return it
    return ''.join(result)

Edge Cases Handled

  • The code handles cases where s is non-empty, as required by the problem constraints.
  • Since all values in indices are unique and form a permutation of integers from 0 to n-1, there are no additional edge cases related to invalid indices.