Leetcode 1528. Shuffle String

Problem Explanation:

In this problem, we are given a string s and an array called indices which dictates how the string should be shuffled. That is, the character at the i-th position in the string s should be moved to the indices[i]-th position in the newly shuffled string. Our aim is to follow the order given by the indices array and shuffle the string accordingly.

Let's understand this with an example.

Suppose s = "codeleet" and indices = [4,5,6,7,0,2,1,3]. Now, the character at 0-th position in s is 'c' which should be moved to the 4th position in the shuffled string. Similarly, the character at 1-st position in s is 'o' which should be moved to the 5th position in the shuffled string, following the same pattern, the final shuffled string will be "leetcode".

Approach of the Solution:

The solution uses a simple for-loop to iterate over the indices array and re-arranges the characters in the string as per the given indices. It uses an auxiliary string 'ans' of the same length as string s and initially filled with '.' . For every character at i-th position in the string s, it assigns the character at the indices[i]-th position in the 'ans' string. Finally, it returns the 'ans' string which is the desired shuffled string.

Now, let's see how the algorithm works step-by-step:

Assuming the input string s = "codeleet" and indices = [4,5,6,7,0,2,1,3], the table below shows the updated 'ans' string after each step.

1
2
3Iteration    Character   From   To   'ans' string
4    0           'c'        0     4   ....c...
5    1           'o'        1     5   ....co..
6    2           'd'        2     6   ....cod.
7    3           'e'        3     7   ....code
8    4           'l'        4     0   l...code
9    5           'e'        5     2   l..ecode
10    6           'e'        6     1   l.eecode
11    7           't'        7     3   leetcode  

Now, let's implement this solution in different programming languages:

Python Solution

1
2python
3class Solution:
4    def restoreString(self, s: str, indices: List[int]) -> str:
5        ans = ['']*len(s)  # Initialize an empty string of same length as 's'
6        for i in range(len(s)):  # Iterate over the string 's'
7            ans[indices[i]] = s[i]  # Assign the character at indices[i] position in 'ans' string
8        return ''.join(ans)  # Convert list of characters to string

Java Solution

1
2java
3public class Solution {
4    public String restoreString(String s, int[] indices) {
5        char[] ans = new char[s.length()]; // Initialize an empty char array of same length as 's'
6        for(int i=0; i<s.length(); i++) { // Iterate over the string 's'
7            ans[indices[i]] = s.charAt(i); // Assign the character at indices[i] position in 'ans' array
8        }
9        return new String(ans); // Convert char array to string
10    }
11}

JavaScript Solution

1
2javascript
3class Solution {
4    restoreString(s, indices) {
5        let ans = new Array(s.length);  // Initialize an empty array of same length as 's'
6        for(let i=0; i<s.length; i++) {  // Iterate over the string 's'
7            ans[indices[i]] = s[i];  // Assign the character at indices[i] position in 'ans' array
8        }
9        return ans.join('');  // Convert array of characters to string
10    }
11}

C++ Solution

1
2c++
3class Solution {
4public:
5    string restoreString(string s, vector<int>& indices) {
6        string ans(s.length(), '.');  // Initialize a string of '.' of same length as 's'
7        for(int i=0; i<s.length(); i++) {  // Iterate over the string 's'
8            ans[indices[i]] = s[i];  // Assign the character at indices[i] position in 'ans' string
9        }
10        return ans;  // Return the shuffle string
11    }
12};

C# Solution

1
2csharp
3public class Solution {
4    public string RestoreString(string s, int[] indices) {
5        char[] ans = new char[s.Length];  // Initialize an empty char array of same length as 's'
6        for(int i=0; i<s.Length; i++) {  // Iterate over the string 's'
7            ans[indices[i]] = s[i];  // Assign the character at indices[i] position in 'ans' array
8        }
9        return new string(ans);  // Convert char array to string
10    }
11}

With this approach, we are shuffling the string in-place and the time complexity is O(n), where n is the length of the string.## Swift Solution

1
2swift
3class Solution {
4    func restoreString(_ s: String, _ indices: [Int]) -> String {
5        var ans = Array(repeating: " ", count: s.count)  // Initialize an array of ' ' of same length as 's'
6        let sArray = Array(s)
7        for i in 0..<s.count {  // Iterate over the string 's'
8            ans[indices[i]] = String(sArray[i])  // Assign the character at indices[i] position in 'ans' array
9        }
10        return ans.joined()  // Convert array of characters to string
11    }
12}

Ruby Solution

1
2ruby
3class Solution
4    def restore_string(s, indices)
5        ans = Array.new(s.length)  // Initialize an empty array of nil of same length as 's'
6        s.each_char.with_index do |char, i|  // Iterate over the string 's'
7            ans[indices[i]] = char  // Assign the character at indices[i] position in 'ans' array
8        end
9        ans.join  // Convert array of characters to string
10    end
11end

In this approach, we created placeholder arrays (ans) with the same size as the input string (s). The elements at the indices based on the indices array are then replaced by the corresponding characters. This approach provides a straightforward way of mutating the placeholder arrays in place with minimal space complexity. We then return ans as a single string using the 'joined' or 'join' function.

This code runs in linear time (O(n)) and uses linear space (O(n)), where 'n' is the size of the input string. This performance is derived from the use of a single loop that iterates through the string and index array.

This concludes our article on the string shuffle problem solved in multiple languages using a simple for-loop approach. We hope you found this article informative and it helps you in your coding journey. Stay tuned for more problem solutions like this!