Code Implementation

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        res = [''] * len(s)
        for char, idx in zip(s, indices):
            res[idx] = char
        return ''.join(res)
      

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string res(s.size(), ' ');
        for (int i = 0; i < s.size(); ++i) {
            res[indices[i]] = s[i];
        }
        return res;
    }
};
      

class Solution {
    public String restoreString(String s, int[] indices) {
        char[] res = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            res[indices[i]] = s.charAt(i);
        }
        return new String(res);
    }
}
      

var restoreString = function(s, indices) {
    let res = Array(s.length);
    for (let i = 0; i < s.length; i++) {
        res[indices[i]] = s[i];
    }
    return res.join('');
};
      

Problem Description

Given a string s and an integer array indices of the same length, you are to shuffle the string such that the character at the i-th position of s moves to indices[i] in the shuffled string. The goal is to return the shuffled string.

• Each position in indices is unique and between 0 and len(s) - 1.
• You must not reuse characters; each character from s is used once and placed exactly once.
• There is always one valid solution for the input.

Thought Process

To solve this problem, we need to rearrange the characters of s according to the mapping defined by indices. The most straightforward way is to create a new result array or string and place each character from s into its target position as specified by indices.

Initially, one might consider generating all possible permutations and checking which one matches the mapping, but this would be extremely inefficient. Instead, by directly using the mapping given by indices, we can reconstruct the answer in a single pass.

Solution Approach

Here is a step-by-step approach to solving this problem efficiently:

1. Create a result array: Start by creating an array (or string in languages where strings are mutable) of the same length as s, initialized with empty values.
2. Iterate through the input: For each character in s, use its corresponding value in indices to determine its new position in the result array.
3. Assign characters: Set result[indices[i]] = s[i] for each position i.
4. Build the final string: After all characters are assigned, join the result array into a string and return it.

This method is efficient because it only requires a single pass through the input and uses direct indexing, which is an O(1) operation.

Example Walkthrough

Suppose s = "code" and indices = [3, 1, 2, 0]. Let's walk through the solution step by step:

• Initialize result = ["", "", "", ""].
• For i = 0: s[0] = "c", indices[0] = 3 → result[3] = "c" → ["", "", "", "c"]
• For i = 1: s[1] = "o", indices[1] = 1 → result[1] = "o" → ["", "o", "", "c"]
• For i = 2: s[2] = "d", indices[2] = 2 → result[2] = "d" → ["", "o", "d", "c"]
• For i = 3: s[3] = "e", indices[3] = 0 → result[0] = "e" → ["e", "o", "d", "c"]

Finally, joining the array gives "eodc".

Time and Space Complexity

• Brute-force approach: Generating all permutations and checking each would take O(n!) time and O(n) space, which is infeasible for even moderately sized inputs.
• Optimized approach (used here): We make a single pass through s and indices, placing each character in its correct position. This is O(n) time and O(n) space, where n is the length of the string.

The O(n) time comes from iterating through the arrays once, and the O(n) space is for the result array.

Summary

The solution leverages direct indexing to efficiently rearrange the string according to the mapping provided by indices. By avoiding brute-force permutations and instead using an auxiliary array to reconstruct the answer, the approach is both simple and optimal. This problem is a great example of how understanding the mapping between inputs can lead to an elegant O(n) solution.