algoadvance

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 i-th position moves to indices[i] in the shuffled string. Return the shuffled string.

Example:

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

Clarifying Questions:

1. Can we assume the length of s and indices are always the same?
   • Yes, the problem guarantees this.
2. Are the integers in indices always unique and within the range [0, len(s)-1]?
   • Yes.
3. Should we handle any special characters or specific types of inputs?
   • No, the string will consist of printable ASCII characters.

Strategy:

1. Initialize an empty list shuffled of the same length as s.
2. Iterate over the indices array:
   • For each index i, place the character s[i] at the position indices[i] in the shuffled list.
3. Join the shuffled list into a string and return it.

Time Complexity:

• The time complexity of this approach is (O(n)), where (n) is the length of the string s. This is because we are iterating through the list once and performing constant-time operations for each character.

Code:

def restoreString(s, indices):
    # Initialize a list of the same length as s with empty strings
    shuffled = [''] * len(s)
    
    # Place each character at its new index
    for i in range(len(s)):
        shuffled[indices[i]] = s[i]
    
    # Join the list into a string and return
    return ''.join(shuffled)

# Example usage
s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
print(restoreString(s, indices))  # Output: "leetcode"

This code creates a new list shuffled which stores the characters of s rearranged according to the indices list, and then returns the joined string.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?