Shuffle String

Easy
225.

Shuffle String

Shuffle String is an easy coding problem on arrays and strings, asked in Amazon and Microsoft interviews.

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 <= 40
  • indices.length == s.length
  • indices is a permutation of 0 … s.length - 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[]} indices
 * @return {string}
 */
var restoreString = function(s, indices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • indices.length == s.length
  • indices is a permutation of 0 … s.length - 1.

Hints for Shuffle String

  1. Hint 1

    Allocate the answer up front and write each character straight into its destination slot.

  2. Hint 2

    Do not confuse the two directions: indices[i] is where character i goes, not where it comes from.

How to solve Shuffle String

Allocate the output and write each character directly to its destination indices[i].

Approach

  1. Create an array of n empty slots.
  2. For each i, set out[indices[i]] = s[i].
  3. 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 slot i applies 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings