Shuffle String
Easy
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<sup>th</sup> position moves to indices[i] in the shuffled string.
Return the shuffled string.
Example 1:
s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.
Example 2:
s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.
Can you implement a function that takes the string s and the integer array indices as input and returns the shuffled string? Consider the time and space complexity of your solution. How would you handle edge cases, such as an empty input string or invalid indices?
Solution
Naive Solution
A brute-force approach would involve creating a new string of the same length as the input string s. Iterate through the input string s and the indices array. For each index i, place the character s[i] at the position indices[i] in the new string. Finally, return the new string.
Example:
s = "codeleet", indices = [4, 5, 6, 7, 0, 2, 1, 3]
- Create an empty string of length 8:
" " s[0] = 'c',indices[0] = 4. Place'c'at index 4:" c "s[1] = 'o',indices[1] = 5. Place'o'at index 5:" co "- Continue this process until all characters are placed.
- Result:
"leetcode"
Code (Python)
def restore_string_naive(s: str, indices: list[int]) -> str:
n = len(s)
shuffled_string = [''] * n
for i in range(n):
shuffled_string[indices[i]] = s[i]
return ''.join(shuffled_string)
Big O Runtime
The time complexity is O(n), where n is the length of the string, as we iterate through the string once.
Big O Space
The space complexity is O(n), as we create a new string of the same length as the input string to store the shuffled string.
Optimal Solution
The optimal solution does not differ significantly from the naive approach in terms of time and space complexity. However, we can consider this the optimal approach, because it directly addresses the problem's requirements with the simplest possible code.
Code (Python)
def restore_string(s: str, indices: list[int]) -> str:
n = len(s)
shuffled_string = [''] * n
for i in range(n):
shuffled_string[indices[i]] = s[i]
return ''.join(shuffled_string)
Big O Runtime
The time complexity remains O(n), where n is the length of the string.
Big O Space
The space complexity remains O(n), due to the creation of the shuffled_string list.
Edge Cases
- Empty string: If the input string
sis empty, the code should handle it gracefully. In the provided solution, an empty string will result in an empty list and an empty string being returned, which is the expected behavior. - Invalid indices: The problem states that all values of
indicesare unique and within the range[0, n). If these constraints were not met, we would need to add error handling to check for out-of-bounds indices or duplicate indices. However, based on the problem statement, we can assume the input is valid. - Single character string: if the string is only a single character, the algorithm should work without issues.
