algoadvance

Leetcode 1528. Shuffle String

Problem Statement

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.

Example 1:

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

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"

Clarifying Questions

  1. What is the length range of the string s?
    • The string length can vary within typical constraints of interview problems (e.g., 1 ≤ s.length ≤ 100).
  2. Are all the elements in the indices array unique?
    • Yes, since indices is a permutation of the array 0 to n-1.
  3. What should be returned if the input string is empty?
    • Return an empty string if the input string is empty.

Strategy

  1. Create a character array shuffled of the same length as s.
  2. Iterate through the string s and place each character to its correct index as specified in the indices array.
  3. Convert the character array shuffled back to a string and return it.

Code

public class ShuffleString {
    public String restoreString(String s, int[] indices) {
        // Create a character array to hold the shuffled version
        char[] shuffled = new char[s.length()];

        // Iterate over the input string and place each character to its new position
        for (int i = 0; i < s.length(); i++) {
            shuffled[indices[i]] = s.charAt(i);
        }

        // Convert the character array back to a string
        return new String(shuffled);
    }

    public static void main(String[] args) {
        ShuffleString shuffleString = new ShuffleString();
        System.out.println(shuffleString.restoreString("codeleet", new int[]{4,5,6,7,0,2,1,3})); // Outputs: "leetcode"
        System.out.println(shuffleString.restoreString("abc", new int[]{0,1,2})); // Outputs: "abc"
    }
}

Time Complexity

This implementation ensures that the string is shuffled correctly based on the provided indices array in linear time, making it efficient for typical input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI