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
scontaining only lowercase English letters. - An integer array
indiceswhere each element indicates the new position of the character from the same index ins.
Outputs:
- A new string that represents the shuffled version of
s.
Implicit Constraints or Tricky Edge Cases:
- The length of
sis equal to the length ofindices. - All values in
indicesare unique and form a permutation of integers from 0 to n-1. - The string
scan be empty, but since the problem specifies1 <= 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
- Initialize an empty list
resultof the same length ass. - Iterate through each character in
sand its corresponding index. - Place each character at the position specified by
indices[i]in theresultlist. - 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
sis non-empty, as required by the problem constraints. - Since all values in
indicesare unique and form a permutation of integers from 0 to n-1, there are no additional edge cases related to invalid indices.