LeetCode 1528 - Shuffle String

LeetCode Problem 1528

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to take a string s and an integer array indices of the same length, and produce a new string where each character in s is moved to the position specified by indices. In other words, for each index i in s, the character s[i] should be placed at position indices[i] in the resulting string. The output is the fully rearranged string after applying this mapping.

The constraints provide important guarantees: s and indices have the same length n, which ranges from 1 to 100, all values in indices are unique, and every value is within the valid range [0, n-1]. These guarantees ensure that every character has a unique target position and there are no duplicates or out-of-bound indices, simplifying the implementation. Edge cases to be mindful of include the smallest possible string (length 1), strings that are already in order, and strings that require full reversal or complex shuffling.

Approaches

A brute-force approach would iterate through each character in s and repeatedly insert it into a new string or list at the corresponding index. While this approach is simple and correct, repeatedly inserting into a string in languages like Python can be inefficient because strings are immutable, leading to O(n²) time complexity in the worst case. Using a list mitigates this, but the brute-force idea is still more complex than necessary.

The optimal approach leverages the key observation that we can directly place each character into its target position in a pre-allocated array or slice of the correct size. By iterating once over s and indices, we can fill this array in O(n) time, then join the array into a final string. This approach is straightforward and avoids unnecessary repeated operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Inserting characters into a string repeatedly, inefficient for long strings
Optimal	O(n)	O(n)	Pre-allocate array and place characters directly at target indices

Algorithm Walkthrough

1. Initialize an array or slice result of length n, filled with placeholder characters (or empty values).
2. Iterate through the string s using an index i.
3. For each character s[i], retrieve its target position from indices[i].
4. Place s[i] directly into result[indices[i]].
5. After the loop completes, convert result back into a string by joining all characters in order.
6. Return the resulting string.

Why it works: This algorithm works because each index in indices is unique and within bounds. The invariant is that for each i, result[indices[i]] contains s[i]. Since all indices are unique and we iterate exactly once, no characters overwrite each other, guaranteeing correctness.

Python Solution

from typing import List

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)

In this Python implementation, we first create a list result of the same length as s, initially filled with empty strings. We iterate through s using the index i and place each character in its target position using indices[i]. Finally, we convert the list back into a string using join and return it.

Go Solution

func restoreString(s string, indices []int) string {
    n := len(s)
    result := make([]byte, n)
    for i := 0; i < n; i++ {
        result[indices[i]] = s[i]
    }
    return string(result)
}

In Go, we allocate a byte slice result with the same length as s. We iterate through s and assign each byte to the correct index from indices. Finally, we convert the byte slice back to a string and return it. Go requires handling the string as a byte slice because strings are immutable, similar to Python.

Worked Examples

Example 1:

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

i	s[i]	indices[i]	result state
0	c	4	['', '', '', '', 'c', '', '', '']
1	o	5	['', '', '', '', 'c', 'o', '', '']
2	d	6	['', '', '', '', 'c', 'o', 'd', '']
3	e	7	['', '', '', '', 'c', 'o', 'd', 'e']
4	l	0	['l', '', '', '', 'c', 'o', 'd', 'e']
5	e	2	['l', '', 'e', '', 'c', 'o', 'd', 'e']
6	e	1	['l', 'e', 'e', '', 'c', 'o', 'd', 'e']
7	t	3	['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']

Final string: "leetcode"

Example 2:

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

Each character stays in place, so the result is "abc".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate over the string exactly once and perform constant-time assignments
Space	O(n)	We allocate a new array/slice of the same length as the input string

The complexity is efficient given the constraints, with a single linear pass and linear space usage. Since n <= 100, this is very fast in practice.

Test Cases

# Provided examples
assert Solution().restoreString("codeleet", [4,5,6,7,0,2,1,3]) == "leetcode"  # example 1
assert Solution().restoreString("abc", [0,1,2]) == "abc"  # example 2

# Boundary cases
assert Solution().restoreString("a", [0]) == "a"  # single character
assert Solution().restoreString("ab", [1,0]) == "ba"  # simple swap
assert Solution().restoreString("xyz", [2,0,1]) == "yzx"  # arbitrary shuffle

# Stress case
s = ''.join(chr(97 + i) for i in range(26))
indices = list(range(25, -1, -1))
assert Solution().restoreString(s, indices) == s[::-1]  # reverse the alphabet

Test	Why
"codeleet"	Tests general shuffle and multiple moves
"abc"	Tests identity mapping (no change)
"a"	Smallest input, single character
"ab"	Tests swap of two elements
"xyz"	Tests arbitrary shuffle
Alphabet reverse	Tests maximum size for n with a reverse pattern

Edge Cases

The first edge case is when the input string has length 1. In this situation, the algorithm must correctly handle a trivial mapping, ensuring the single character stays in its place. Since the indices array will also be [0], the algorithm naturally places it correctly without errors.

The second edge case involves the input string being already in order. If indices is [0, 1, 2, ..., n-1], the algorithm must leave the string unchanged. The implementation handles this gracefully because the direct assignment of each character to its existing position does not alter it.

The third edge case is a full reversal or complex shuffle, where each character moves to a new position, possibly including the first and last characters. The algorithm correctly handles this because it places each character in its designated position according to indices, and the uniqueness guarantee ensures no overwriting occurs.