Shuffle String Leetcode Solution

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:

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.

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”.

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