Shuffle String

Difficulty: Easy | Acceptance: 85.40% | Paid: No Topics: Array, String

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.

Table of Contents

• Examples
• Constraints
• Direct Array Placement
• Sorting with Pairs
• Using a Map

Examples

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 == n
1 <= n <= 100
s consists of only lowercase English letters.
0 <= indices[i] < n
All values of indices are unique.

Direct Array Placement

Intuition Create a result array and place each character directly at its target position based on the indices array.

Steps

• Create a character array of the same length as s
• Iterate through each index i, placing s[i] at result[indices[i]]
• Convert the character array to a string and return

class Solution:
    def restoreString(self, s: str, indices: list[int]) -> str:
        n = len(s)
        result = [''] * n
        for i in range(n):
            result[indices[i]] = s[i]
        return ''.join(result)

Complexity

• Time: O(n) - Single pass through the string
• Space: O(n) - Result array of size n
• Notes: Most efficient approach for this problem

Sorting with Pairs

Intuition Create pairs of (index, character) and sort them by index to get the correct order.

Steps

• Create an array of pairs containing (indices[i], s[i])
• Sort the pairs based on the index value
• Extract characters in order to form the result string

class Solution:
    def restoreString(self, s: str, indices: list[int]) -> str:
        pairs = list(zip(indices, s))
        pairs.sort()
        return ''.join(char for _, char in pairs)

Complexity

• Time: O(n log n) - Due to sorting
• Space: O(n) - For storing pairs
• Notes: Less efficient than direct placement but demonstrates sorting technique

Using a Map

Intuition Use a hash map to store the mapping from target index to character, then build the result by iterating through indices in order.

Steps

• Create a map/dictionary with indices[i] as key and s[i] as value
• Iterate from 0 to n-1, fetching characters from the map
• Build and return the result string

class Solution:
    def restoreString(self, s: str, indices: list[int]) -> str:
        index_map = {}
        for i, char in enumerate(s):
            index_map[indices[i]] = char
        return ''.join(index_map[i] for i in range(len(s)))

Complexity

• Time: O(n) - Two passes through the data
• Space: O(n) - For the hash map
• Notes: Similar efficiency to direct placement but with more overhead