Problem Description

You are given a string s and an integer array indices where both have the same length. Your task is to rearrange the characters of the string based on the positions specified in the indices array.

The shuffling works as follows: the character currently at position i in the original string s should be moved to position indices[i] in the final shuffled string.

For example, if s = "abc" and indices = [2, 0, 1]:

• The character at position 0 ('a') moves to position indices[0] = 2
• The character at position 1 ('b') moves to position indices[1] = 0
• The character at position 2 ('c') moves to position indices[2] = 1
• The resulting shuffled string would be "bca"

The solution creates an array ans of the same length as the input string. It then iterates through each character in the original string along with its index i. For each character c at position i, it places that character at position indices[i] in the answer array. Finally, it joins all characters in the answer array to form the shuffled string.

The time complexity is O(n) where n is the length of the string, as we iterate through the string once. The space complexity is also O(n) for storing the result array.

Intuition

The key insight is to understand what the indices array is telling us. Each value indices[i] represents the destination position for the character at position i in the original string.

Instead of trying to track where each character comes from, we can directly place each character where it needs to go. Think of it like having a set of letters and an instruction manual that tells you exactly where to place each letter.

When we see that indices[i] = j, this means "take the character at position i and put it at position j in the result". This is a direct mapping relationship.

The natural approach is to:

1. Create an empty result array of the same size as our string
2. Go through each character in the original string one by one
3. For each character at position i, look up where it should go (indices[i])
4. Place that character directly at its destination position

This works because the indices array guarantees that each position from 0 to n-1 appears exactly once (it's a permutation), ensuring every position in our result will be filled with exactly one character.

The beauty of this solution is its simplicity - we don't need to reverse any mappings or perform complex swaps. We simply read the instructions and place each character exactly where it belongs in a single pass through the string.

Solution Approach

The implementation follows a straightforward direct placement strategy:

1. Initialize Result Array: Create an array ans of the same length as the input string s. Initially, we can fill it with any placeholder values (here using 0), as all positions will be overwritten.

   ans = [0] * len(s)

2. Iterate and Place Characters: Use enumerate() to iterate through the string s, which gives us both the index i and the character c at that position.

   for i, c in enumerate(s):

3. Direct Placement: For each character c at position i, place it directly at its destination position indices[i] in the result array.

   ans[indices[i]] = c

   This is the core operation - we're using indices[i] as the index to determine where character c should go in the final arrangement.

4. Convert to String: After all characters have been placed in their correct positions, join the array elements to form the final string.

   return ''.join(ans)

Example Walkthrough: If s = "codeleet" and indices = [4,5,6,7,0,2,1,3]:

• Character 'c' at position 0 goes to position 4: ans[4] = 'c'
• Character 'o' at position 1 goes to position 5: ans[5] = 'o'
• Character 'd' at position 2 goes to position 6: ans[6] = 'd'
• And so on...

After processing all characters, ans = ['l','e','e','t','c','o','d','e'], which joins to form "leetcode".

The algorithm uses an array as the primary data structure for efficient O(1) access when placing characters at specific positions. The pattern here is index mapping - using one array's values as indices for another array.

Example Walkthrough

Let's walk through a small example with s = "cab" and indices = [2, 0, 1].

Step 1: Initialize Result Array

• Create an array ans with length 3 (same as string length)
• ans = [_, _, _] (placeholders shown as underscores)

Step 2: Process Each Character

Iteration 1 (i=0):

• Current character: c at position 0
• Destination: indices[0] = 2
• Place 'c' at position 2: ans[2] = 'c'
• Result: ans = [_, _, 'c']

Iteration 2 (i=1):

• Current character: a at position 1
• Destination: indices[1] = 0
• Place 'a' at position 0: ans[0] = 'a'
• Result: ans = ['a', _, 'c']

Iteration 3 (i=2):

• Current character: b at position 2
• Destination: indices[2] = 1
• Place 'b' at position 1: ans[1] = 'b'
• Result: ans = ['a', 'b', 'c']

Step 3: Convert to String

• Join the array: ''.join(['a', 'b', 'c'])
• Final result: "abc"

The key insight: each indices[i] value tells us exactly where the character at position i should go in the final string. We simply follow these instructions directly, placing each character at its designated spot.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s.

• The code iterates through the string once using enumerate(s), which takes O(n) time
• Each iteration performs a constant time operation of assigning a character to a specific index in the ans array
• The ''.join(ans) operation at the end also takes O(n) time to concatenate all characters
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the string s.

• The ans list is created with size n to store the rearranged characters, requiring O(n) space
• The output string created by ''.join(ans) also requires O(n) space, but this is typically considered part of the output and not counted as auxiliary space
• No other significant auxiliary space is used
• Total auxiliary space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing the Direction of Index Mapping

The most common mistake is misunderstanding which way the index mapping works. Many people initially think that indices[i] tells us where to get the character FROM, rather than where to PUT the character TO.

Incorrect Understanding:

# WRONG: This treats indices[i] as the source position
result[i] = s[indices[i]]  # This would be incorrect!

Correct Understanding:

# RIGHT: indices[i] tells us the destination for s[i]
result[indices[i]] = s[i]

Example to Illustrate the Difference:

• Given s = "abc" and indices = [2, 0, 1]
• Wrong approach would produce: result[0] = s[2] = 'c', result[1] = s[0] = 'a', result[2] = s[1] = 'b' → "cab"
• Correct approach produces: result[2] = s[0] = 'a', result[0] = s[1] = 'b', result[1] = s[2] = 'c' → "bca"

2. Using String Concatenation Instead of List

Building the result using string concatenation is inefficient and can lead to errors when trying to assign to specific indices:

Inefficient/Error-prone:

result = ""
for i, c in enumerate(s):
    result[indices[i]] = c  # ERROR: strings are immutable!

Better Approach:

result = [''] * len(s)  # Use a list for O(1) index assignment
for i, c in enumerate(s):
    result[indices[i]] = c
return ''.join(result)

3. Not Handling Edge Cases

While the problem typically guarantees valid input, in real scenarios you might want to validate:

• Empty string or empty indices array
• Mismatched lengths between s and indices
• Invalid indices (duplicates or out of range)

Robust Solution with Validation:

def restoreString(self, s: str, indices: List[int]) -> str:
    # Validate input
    if not s or not indices:
        return s
  
    if len(s) != len(indices):
        raise ValueError("String and indices must have the same length")
  
    # Check for valid indices (optional validation)
    if len(set(indices)) != len(indices) or min(indices) < 0 or max(indices) >= len(s):
        raise ValueError("Invalid indices array")
  
    result = [''] * len(s)
    for i, c in enumerate(s):
        result[indices[i]] = c
  
    return ''.join(result)