Shuffle String | LeetCode Problems And Solution

Shuffle String is one of the easiest problems on LeetCode, but it is a clean way to understand a pattern that shows up again and again: placing items by index into a new array. You are not searching or sorting anything. You are just reading a "where does this go" instruction for each character and following it.

The one thing to get right is the direction of the mapping. Many beginners read indices[i] as "take the character from this position", which gives a different string. Once that is clear, the solution is a single loop.

Problem

You have a string s and an integer array indices of the same length. The character currently at position i in s needs to be moved to position indices[i] in the result. Build and return the rearranged string.

Input: a string s and an array indices.

Output: the shuffled string.

Constraints:

• s.length == indices.length == n, with 1 ≤ n ≤ 100.
• s has only lowercase English letters.
• 0 ≤ indices[i] < n, and all values in indices are different, so it is a permutation of 0 to n - 1.

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

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Approach

Think of an empty row of n boxes. Go through s from left to right. For each character, indices tells you which box it goes into. Since every index is different, each box gets exactly one character and nothing is overwritten.

1. Create a char[] result of length n.
2. For each i from 0 to n - 1, set result[indices[i]] = s.charAt(i).
3. Turn the char array into a String and return it.

Dry run with s = "aiohn", indices = [3,1,4,2,0]:

• 'a' (i = 0) goes to box 3.
• 'i' (i = 1) goes to box 1.
• 'o' (i = 2) goes to box 4.
• 'h' (i = 3) goes to box 2.
• 'n' (i = 4) goes to box 0.

Reading boxes 0 to 4 gives n, i, h, a, o, which is "nihao".

The wrong direction would be result[i] = s.charAt(indices[i]). For "codeleet" it gives "leetcdoe", which is close enough to fool you at a glance, and for "aiohn" it gives "hinoa". Always check your direction on the first example, letter by letter.

Solution in Java

class Solution {
    public String restoreString(String s, int[] indices) {
        char[] result = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            // the character at position i belongs at position indices[i]
            result[indices[i]] = s.charAt(i);
        }
        return new String(result);
    }

    // Small driver for local testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.restoreString("codeleet", new int[]{4, 5, 6, 7, 0, 2, 1, 3}));
        System.out.println(sol.restoreString("abc", new int[]{0, 1, 2}));
        System.out.println(sol.restoreString("aiohn", new int[]{3, 1, 4, 2, 0}));
        System.out.println(sol.restoreString("art", new int[]{1, 0, 2}));
        System.out.println(sol.restoreString("z", new int[]{0}));
        System.out.println(sol.restoreString("abcd", new int[]{3, 2, 1, 0}));
    }
}

On LeetCode you submit only the restoreString method. The old version of this post had the same idea in Java and Python, and both were correct. Here is the Python version written out cleanly, since the original post included one:

class Solution:
    def restoreString(self, s, indices):
        result = [""] * len(s)
        for ch, pos in zip(s, indices):
            result[pos] = ch          # character goes to its target slot
        return "".join(result)

print(Solution().restoreString("codeleet", [4, 5, 6, 7, 0, 2, 1, 3]))
print(Solution().restoreString("aiohn", [3, 1, 4, 2, 0]))
print(Solution().restoreString("abcd", [3, 2, 1, 0]))

Besides the examples, I tested a single character ("z" with [0], which stays "z"), the identity case ("abc" with [0,1,2]), and a full reversal ("abcd" with [3,2,1,0], which gives "dcba").

Output

leetcode
abc
nihao
rat
z
dcba

The Python version prints leetcode, nihao and dcba for its three test calls.

Complexity

Time: O(n). One pass to place characters and one to build the String.

Space: O(n) for the result array. You cannot avoid this in Java, because Strings are immutable.

Common mistakes

• Reversing the mapping and writing result[i] = s.charAt(indices[i]). That applies the inverse permutation.
• Building the answer with result += ch in a loop. You cannot insert at a random position that way, and repeated String concatenation creates a new String each time.
• Using result.toString() on a char[]. That prints something like [C@1b6d3586. Use new String(result) or String.valueOf(result).
• Trying to swap characters in place without care. It can be done with cycle-following, but it is easy to get wrong and saves nothing at n ≤ 100.

Other easy LeetCode posts on the site: Detect Capital and Find Lucky Integer in an Array.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More LeetCode solutions All coding problems MCQ practice