Shuffle String Leetcode Solution  

Difficulty Level Easy
Frequently asked in Facebook
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Sorting

Problem statement  

In the problem ” Shuffle String” we are given a String and an array. The array contains the new indices of the character of the string. So array[i] represents a new position of character at ith position of the string.

In “Shuffle String”  we need to shuffle the characters of the string in such a way that ith character of the string is moved to indices[i]th position and return the new shuffled string.

Example

s = "art", indices = [1,0,2]
rat

Explanation:

the new position of characters are as follows:

Please click Like if you loved this article?

a->1

r->0

t->2

So after shuffling the characters shuffled string is rat.

Approach for Shuffle String Leetcode Solution  

The ” Shuffle String ” problem is basically an implementation problem where we need to focus more on the implementation part. Here we have to assign a character that is present at the ith position to indices[i]th position. This will be more clear from the below image.

leetcode solution to Shuffle StringPin

As it is shown in the image “a” is moved to index number 1, “r” is moved to index number 0, and “t” is moved to index number 2. So the final string after performing shuffle operation it becomes “rat”.

See also
Add Binary Leetcode Solution

So we will use a new string variable to store the result and initialize it with the original string. let’s call it result string. Now we will traverse the indices array and will assign character at ith position to result[indices[i]].

At the end, the result string will contain the new shuffled string.

Implementation

C++ code for Shuffle String

#include <bits/stdc++.h> 
using namespace std; 
     string restoreString(string s, vector<int>& indices) {
        string res = s;
        for(int i =0; i < indices.size(); ++i)
            res[indices[i]] = s[i];
        return res;
    }
int main() 
{ 
 string s="art";      
 vector<int> arr = { 1,0,2 }; 
 cout<<restoreString(s,arr)<<endl; 
 return 0;
}
rat

Java code for Shuffle String

import java.util.Arrays; 
public class Tutorialcup {
    public static  String restoreString(String s, int[] indices) {
        StringBuilder res = new StringBuilder(s);
        for(int i =0; i < indices.length; ++i)
             res.setCharAt(indices[i],s.charAt(i));
        return res.toString();
    }
  public static void main(String[] args) {
    String s="art";  
    int [] arr = {1,0,2}; 
    String ans=  restoreString(s,arr);
    System.out.println(ans);
  }
}
rat

Complexity Analysis of Shuffle String Leetcode Solution  

Time complexity

The time complexity of the above code is O(n) because we are traversing the indices only once. Here n represents the number of characters in the string.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Please click Like if you loved this article?