#1528

Easy

LeetCode Problem Workspace

Shuffle String

Reorder characters in a string using a given indices array to reconstruct the intended output efficiently and correctly.

array string

Problem Statement

You are given a string s and an integer array indices of the same length. Each character at position i in s must be moved to position indices[i] in the resulting string. Your task is to reconstruct and return the shuffled string according to these rules.

For example, given s = "codeleet" and indices = [4,5,6,7,0,2,1,3], the output should be "leetcode" because each character is relocated to its mapped index. Ensure your solution handles strings of any length within the constraints and preserves all characters exactly once.

Examples

Example 1

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]

Output: "leetcode"

As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2

Input: s = "abc", indices = [0,1,2]

Output: "abc"

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.

Solution Approach

Auxiliary Array Mapping

Create an empty array of the same length as s. Iterate over s and place each character at the position specified in indices. Join the array into a string and return. This method leverages direct mapping to avoid overwriting errors.

In-Place Swap with Tracking

For advanced optimization, iterate through s and swap characters into their target positions using indices, marking visited positions to prevent cycles. This reduces extra space usage but requires careful handling of already positioned characters.

One-Pass List Comprehension

Use a comprehension to build the result by directly indexing s according to the sorted order of indices. This is concise, readable, and maintains O(n) time complexity while emphasizing the array plus string pattern central to the problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is moved exactly once. Space complexity is O(n) if using an auxiliary array; in-place swaps can reduce space to O(1) but add bookkeeping overhead. The primary cost comes from handling the array mapping efficiently without collisions or overwrites.

What Interviewers Usually Probe

Do you recognize that direct mapping from indices is the simplest approach?
Have you considered space-efficient in-place rearrangement versus auxiliary array?
Can you handle edge cases like already sorted or reversed indices arrays?

Common Pitfalls or Variants

Common pitfalls

Overwriting characters without tracking positions leading to incorrect results.
Confusing indices positions with string positions during iteration.
Ignoring constraints on unique indices causing unexpected duplication or gaps.

Follow-up variants

Shuffle string with repeated characters and duplicate index handling.
Shuffle string with partial indices and leaving some characters in place.
Shuffle string in-place without using extra array to minimize space complexity.

FAQ

What is the simplest approach to solve Shuffle String?

Use an auxiliary array of the same length as s and place each character at its target index from indices, then join into a string.

Can Shuffle String be solved in-place without extra space?

Yes, but you must track visited positions to avoid overwriting characters, which adds complexity.

What mistakes do people commonly make with indices mapping?

A frequent error is treating string positions and indices interchangeably, which can misplace characters.

How does GhostInterview improve solving array plus string problems?

It guides you to map elements correctly using indices and highlights potential overwrites or tracking errors for safe execution.

Are there variations of Shuffle String for interviews?

Yes, including cases with repeated characters, partial indices, or in-place space-optimized shuffling.

terminal

Solution

Solution 1: Simulation

We create a character array or string $\textit{ans}$ of the same length as the input string, then iterate through the string $\textit{s}$ and place each character $\textit{s}[i]$ at position $\textit{indices}[i]$ in $\textit{ans}$. Finally, we join the character array or string $\textit{ans}$ to form the final result and return it.

1

2

3

4

5

6

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        ans = [None] * len(s)
        for c, j in zip(s, indices):
            ans[j] = c
        return "".join(ans)

Continue Practicing

#1487 making file names unique #1578 minimum time to make rope colorful #1598 crawler log folder