Shuffle String Solution

In this page, we will solve the Shuffle String problem using different approaches: simple iteration and an optimized version using map. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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.

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.

---

Solution for Shuffle String Problem

Intuition and Approach

The problem can be solved by creating a new array for the shuffled string, placing each character at the position specified by the indices array. We will demonstrate a simple iteration approach and an optimized version using map.

• Simple Iteration
• Using Map

Approach 1: Simple Iteration

We iterate through the string and place each character at the position specified by the indices array.

Implementation

Live Editor

function shuffleString() {
  const s = "codeleet";
  const indices = [4, 5, 6, 7, 0, 2, 1, 3];

  const restoreString = function(s, indices) {
    let shuffled = new Array(s.length);
    for (let i = 0; i < s.length; i++) {
      shuffled[indices[i]] = s[i];
    }
    return shuffled.join('');
  };

  const result = restoreString(s, indices);
  return (
    <div>
      <p>
        <b>Input:</b> s = "{s}", indices = {JSON.stringify(indices)}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result

Loading...

Code in Different Languages

JavaScript

Written by @manishh12

 function restoreString(s, indices) {
   let shuffled = new Array(s.length);
   for (let i = 0; i < s.length; i++) {
     shuffled[indices[i]] = s[i];
   }
   return shuffled.join('');
 }

TypeScript

Written by @manishh12

 function restoreString(s: string, indices: number[]): string {
   let shuffled: string[] = new Array(s.length);
   for (let i = 0; i < s.length; i++) {
     shuffled[indices[i]] = s[i];
   }
   return shuffled.join('');
 }

Python

Written by @manishh12

 class Solution:
     def restoreString(self, s: str, indices: List[int]) -> str:
         shuffled = [''] * len(s)
         for i, index in enumerate(indices):
             shuffled[index] = s[i]
         return ''.join(shuffled)

Java

Written by @manishh12

 class Solution {
     public String restoreString(String s, int[] indices) {
         char[] shuffled = new char[s.length()];
         for (int i = 0; i < s.length(); i++) {
             shuffled[indices[i]] = s.charAt(i);
         }
         return new String(shuffled);
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     string restoreString(string s, vector<int>& indices) {
         string shuffled(s.length(), ' ');
         for (int i = 0; i < s.length(); i++) {
             shuffled[indices[i]] = s[i];
         }
         return shuffled;
     }
 };

Complexity Analysis

• Time Complexity: $O(n)$, where n is the length of the string.
• Space Complexity: $O(n)$, as we are using an additional array to store the shuffled string.

Note

By using both simple iteration and map-based approaches, we can efficiently solve the Shuffle String problem. The choice between the two approaches depends on the specific requirements and constraints of the problem.

References

• LeetCode Problem: Shuffle String
• Solution Link: Shuffle String Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta