Shuffle String solution and explanation
Google
9 more videos on this problem
Shuffle String (LeetCode 1528) | Full solution with diagrams | Easy ExplanationNikhil Lohia · 10:09 · 8K views
Leetcode | 1528. Shuffle String | Easy | Java SolutionDeveloper Docs · 4:41 · 3K views
SHUFFLE STRING| Leetcode 1528 | Detailed ExplanationArtificial Minds · 15:50 · 2K views
1528. Shuffle String (Leetcode Easy)Programming Live with Larry · 2:04 · 1K views
LeetCode 1528. Shuffle String Solution Explained - JavaAlgorithms and Data Structures Course · 5:49 · 644 views
Shuffle String | Leetcode #1528 | EasyMorning Byte · 2:10 · 307 views
LeetCode 1528 : Shuffle String | Solution in JAVAAmit Manjarly · 5:21 · 282 views
LeetCode 1528 : Shuffle String | Solution in C++Amit Manjarly · 3:09 · 174 views
Leetcode solving: 1528. Shuffle StringMath Geeks · 2:03 · 96 views
LeetCode | 1528. Shuffle String | RustSergio García Prado · 5:09 · 95 views
The problem
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.
def restoreString(s, indices):
shuffled = [''] * len(s)
for i, char in enumerate(s):
shuffled[indices[i]] = char
return ''.join(shuffled)
s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
print(restoreString(s, indices))import java.util.Arrays;
public class ShuffleString {
public static String restoreString(String s, int[] indices) {
char[] shuffled = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
shuffled[indices[i]] = s.charAt(i);
}
return new String(shuffled);
}
public static void main(String[] args) {
String s = "codeleet";
int[] indices = {4, 5, 6, 7, 0, 2, 1, 3};
System.out.println(restoreString(s, indices));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
string restoreString(string s, vector<int>& indices) {
string shuffled(s.length(), ' ');
for (int i = 0; i < s.length(); i++) {
shuffled[indices[i]] = s[i];
}
return shuffled;
}
int main() {
string s = "codeleet";
vector<int> indices = {4, 5, 6, 7, 0, 2, 1, 3};
cout << restoreString(s, indices) << endl;
return 0;
}function restoreString(s, indices) {
let shuffled = new Array(s.length);
for (let i = 0; i < s.length; i++) {
shuffled[indices[i]] = s[i];
}
return shuffled.join('');
}
let s = "codeleet";
let indices = [4, 5, 6, 7, 0, 2, 1, 3];
console.log(restoreString(s, indices));#include <stdio.h>
#include <string.h>
char *restoreString(char *s, int *indices, int n) {
char *shuffled = (char *)malloc((n + 1) * sizeof(char));
for(int i = 0; i < n; i++) {
shuffled[indices[i]] = s[i];
}
shuffled[n] = '\0';
return shuffled;
}
int main() {
char s[] = "codeleet";
int indices[] = {4, 5, 6, 7, 0, 2, 1, 3};
int n = strlen(s);
char *result = restoreString(s, indices, n);
printf("%s\n", result);
free(result);
return 0;
}using System;
public class ShuffleString {
public static string RestoreString(string s, int[] indices) {
char[] shuffled = new char[s.Length];
for (int i = 0; i < s.Length; i++) {
shuffled[indices[i]] = s[i];
}
return new string(shuffled);
}
public static void Main(string[] args) {
string s = "codeleet";
int[] indices = new int[] {4, 5, 6, 7, 0, 2, 1, 3};
Console.WriteLine(RestoreString(s, indices));
}
}The Python solution uses a list 'shuffled' initialized to the same length as 's' with empty strings. As we iterate through 's', we place each character at the correct index from 'indices'. Finally, we convert the list back to a string using join().
Time Complexity: O(n), iterating through the string once.
Space Complexity: O(n), due to the list used for constructing the result.
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.
def restoreStringInPlace(s, indices):
# Convert the string to a list of characters for in-place swapping
s = list(s)
for i in range(len(s)):
while indices[i] != i:
target = indices[i]
# Swap characters
s[i], s[target] = s[target], s[i]
# Swap the indices to avoid infinite loop
indices[i], indices[target] = indices[target], indices[i]
return ''.join(s)
s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
print(restoreStringInPlace(s, indices))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.
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.
function restoreString(s: string, indices: number[]): string {
const ans: string[] = [];
for (let i = 0; i < s.length; i++) {
ans[indices[i]] = s[i];
}
return ans.join('');
}func restoreString(s string, indices []int) string {
ans := make([]rune, len(s))
for i, c := range s {
ans[indices[i]] = c
}
return string(ans)
}impl Solution {
pub fn restore_string(s: String, indices: Vec<i32>) -> String {
let n = s.len();
let mut ans = vec![' '; n];
let chars: Vec<char> = s.chars().collect();
for i in 0..n {
ans[indices[i] as usize] = chars[i];
}
ans.iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Array Construction | Time Complexity: |
| Approach 2: In-place Array Modification | Time Complexity: |
| Simulation | – |
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. |
Frequently asked questions
Is Shuffle String easy or hard?
Shuffle String is classified as an Easy problem on LeetCode with a high acceptance rate of around 85%. The challenge mainly checks whether you recognize the direct index mapping and implement a linear-time reconstruction.
How to solve Shuffle String in O(n)?
Create a character array of the same length as the input string. Loop through the indices array, and place s[i] into result[indices[i]]. After filling all positions, convert the array to a string. Each element is handled once, giving O(n) time complexity.
What is the best approach for Shuffle String?
The best approach is array construction. Iterate through the string once and place each character s[i] at position indices[i] in a new result array. This solution runs in O(n) time with O(n) space and is the most straightforward method expected in coding interviews.
What data structure is used in Shuffle String?
The main data structure is an array (or character array). The indices array acts as a mapping that determines where each character should move in the final string. No advanced structures like hash maps or trees are required.
What is the time complexity of Shuffle String?
The optimal solution runs in O(n) time because each character is processed exactly once. A result array is filled using direct index mapping from the indices array. Space complexity is O(n) for storing the reconstructed string.
Shuffle String Python or Java solution approach?
Both Python and Java solutions follow the same logic: allocate a result array, iterate through the string, and assign result[indices[i]] = s[i]. Python often uses a list of characters before joining into a string, while Java uses a char array for efficient assignment.
Is Shuffle String asked at Google, Amazon, or Meta?
Shuffle String is an Easy-level array and string manipulation problem commonly used for screening rounds and practice. While not among the most frequently reported problems at top companies, similar index-mapping and permutation problems appear in interviews at companies like Amazon and Google.