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 == n1 <= n <= 100s consists of only lowercase English letters.0 <= indices[i] < nindices are unique.The goal of #1528 Shuffle String is to reconstruct a shuffled string using an index mapping. You are given a string and an array where each position indicates the target index of the corresponding character. The key idea is to place each character directly into its correct position in a new result array.
A common approach is to create a character array of the same length as the input string. Then iterate through the original string, and for each index i, place the character s[i] into the position specified by indices[i]. After processing all characters, convert the array back into a string.
This strategy works efficiently because every character is processed exactly once. The algorithm achieves linear time complexity since it performs a single pass through the input. While the straightforward method uses additional space for the result array, it keeps the implementation simple and reliable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Direct placement using index mapping | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
You can create an auxiliary string t of length n.
Assign t[indexes[i]] to s[i] for each i from 0 to n-1.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Index mapping allows you to directly determine where each character should go in the final string. Instead of sorting or rearranging multiple times, each character is placed once at its correct position.
Yes, Shuffle String is a common beginner-friendly interview problem. It tests understanding of arrays, string manipulation, and basic index mapping techniques.
The optimal approach is to create a result array and place each character from the original string into the position specified by the indices array. This direct mapping method processes each character once, giving O(n) time complexity and O(n) space.
A character array is the most convenient data structure for this problem. It allows direct placement of characters at their correct indices before converting the array back into a string.