Shuffle String - Solution & Explanation
Problem Statement
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 <= 100sconsists of only lowercase English letters.0 <= indices[i] < n- All values of
indicesare unique.
Approach Overview
Problem Overview: You are given a string s and an integer array indices of the same length. Each position in indices tells you where the character at that position in s should appear in the final string. The task is to reconstruct the shuffled string after applying all index mappings.
Approach 1: Array Construction (O(n) time, O(n) space)
The direct solution builds a new character array of size n. Iterate through the string once, and for each index i, place s[i] into position indices[i] of the result array. After the loop finishes, convert the array back to a string. The key insight is that indices already tells you the exact final position of every character, so there is no need for searching or shifting. Every element is processed exactly once, giving O(n) time complexity and O(n) extra space for the result array.
This approach is clean, readable, and works consistently across languages. It relies on basic operations like array indexing and iteration, which makes it ideal when working with arrays and strings. Most production code would use this version because clarity outweighs the small extra memory cost.
Approach 2: In-place Array Modification (O(n) time, O(1) extra space)
You can avoid allocating a separate array by performing swaps until each character reaches its correct index. Iterate through the array, and while indices[i] != i, swap the character at position i with the character at position indices[i]. At the same time, swap the corresponding values in the indices array so the mapping stays consistent. Each swap moves at least one element into its correct position, so the total work remains linear.
This technique treats the problem as a permutation correction. The indices array describes a permutation of positions, and swaps gradually fix cycles in that permutation. Because all rearrangement happens inside the existing arrays, the algorithm runs in O(n) time with O(1) extra space. The tradeoff is slightly more complex logic and careful swap handling.
Recommended for interviews: The array construction approach is what most interviewers expect first. It demonstrates that you quickly recognized the direct mapping between source and destination indices. After presenting it, mentioning the in-place permutation idea shows deeper understanding of array manipulation and space optimization. Interviewers typically accept the O(n) time, O(n) space solution as optimal because it keeps the code simple and avoids unnecessary complexity.
Approach 1: Approach 1: Array Construction
This approach involves iterating over the given string and indices, creating a new array that simulates the shuffled string by placing each character at its target index as specified in the indices array.
The solution uses a new array to shuffle characters. We allocate space for the shuffled string and iterate through the 'indices' array, placing each character from the original string 's' into its new position in 'shuffled.' Finally, remember to null-terminate the shuffled string.
Complexity
Time Complexity: O(n), where n is the length of the string. We iterate over the string once.
Space Complexity: O(n) due to the additional array used for the shuffled string.
Approach 2: Approach 2: In-place Array Modification
This in-place approach involves swapping characters within the original string transformed to a mutable data structure. This technique reduces additional space usage by modifying the existing characters' positions based on indices, ensuring the shuffled sequence is derived directly.
The method involves converting the string into a list for mutable operations. Swapping is performed both on characters and their indices until each character reaches its target position, maintaining a time complexity generally dependent on the swapping constraints rather than individual searches.
Code
Python
Complexity
Time Complexity: O(n) in a typical scenario but can more expensive based on swaps.
Space Complexity: O(1) if the initial space for list conversion is ignored since swaps are in place.
Approach 3: Simulation
We create a character array or string ans of the same length as the input string, then iterate through the string s and place each character s[i] at position indices[i] in ans. Finally, we join the character array or string ans to form the final result and return it.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the string.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Array Construction | Time Complexity: |
| Approach 2: In-place Array Modification | Time Complexity: |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array Construction | O(n) | O(n) | Best general solution. Simple implementation and easy to explain in interviews. |
| In-place Array Modification | O(n) | O(1) | When memory is constrained or when demonstrating knowledge of permutation swaps. |
Video Solution
Shuffle String (LeetCode 1528) | Full solution with diagrams | Easy Explanation • Nikhil Lohia • 8,706 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shuffle String easy or hard?
How to solve Shuffle String in O(n)?
What is the best approach for Shuffle String?
What data structure is used in Shuffle String?
What is the time complexity of Shuffle String?
Shuffle String Python or Java solution approach?
Is Shuffle String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Shuffle String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor