Shuffle String — Solution in Python, Java & C++
Shuffle String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and strings.
Shuffle String is an easy coding problem on arrays and strings, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Strings
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and an integer array indices of the same length. The string was shuffled so that the character originally at position i moved to position indices[i].
Return the restored string.
Example 1
Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: leetcode
Example 2
Input: s = "abc", indices = [0,1,2]
Output: abc
Example 3
Input: s = "aiohn", indices = [3,1,4,2,0]
Output: nihao
Constraints
1 <= s.length <= 40indices.length == s.lengthindices is a permutation of 0 … s.length - 1.
Hints for Shuffle String
Hint 1
Allocate the answer up front and write each character straight into its destination slot.
Hint 2
Do not confuse the two directions:
indices[i]is where characterigoes, not where it comes from.
How to solve Shuffle String
Allocate the output and write each character directly to its destination indices[i].
Approach
- Create an array of
nempty slots. - For each
i, setout[indices[i]] = s[i]. - Join the slots.
Why it works
indices is a permutation, so every slot is written exactly once and the result is well defined.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Reading
s[indices[i]]into slotiapplies the inverse permutation.
Reference solution
Python
def restoreString(s: str, indices) -> str:
out = [""] * len(s)
for i, ch in enumerate(s):
out[indices[i]] = ch
return "".join(out)Java
public static String restoreString(String s, int[] indices) {
char[] out = new char[s.length()];
for (int i = 0; i < s.length(); i++) out[indices[i]] = s.charAt(i);
return new String(out);
}C++
string restoreString(string s, vector<int>& indices) {
string out = s;
for (int i = 0; i < (int) s.size(); i++) out[indices[i]] = s[i];
return out;
}JavaScript
var restoreString = function(s, indices) {
const out = new Array(s.length).fill("");
for (let i = 0; i < s.length; i++) {
out[indices[i]] = s[i];
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.