We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shuffle String

Number: 1651

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given a string s and an integer array indices of the same length, the task is to rearrange s such that the character at the iᵗʰ position in s moves to the position indices[i] in the resulting shuffled string. The goal is to return the shuffled string.

Key Insights

  • The indices array provides a mapping from the original string positions to the target positions.
  • A new result array of the same size can be used to build the shuffled string.
  • Iterating over the characters of s and placing them directly into the correct position is straightforward.
  • The problem can be solved in a single pass which results in optimal time performance.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the string once. Space Complexity: O(n) - We use an additional array (or similar structure) to build the result.

Solution

The solution involves creating a new list (or array) that will store characters in their new positions based on the indices array. For each character in s, we place it at the index specified by indices[i] in the new list. Finally, we convert the list back into a string to get the final shuffled string. The algorithm uses direct indexing which makes it simple and efficient, both in terms of time and space.

Code Solutions

# Python solution for Shuffle String
def restoreString(s: str, indices: list[int]) -> str:
    # Initialize a result list with the same length as s filled with empty strings.
    result = [''] * len(s)
    
    # Iterate through each character and its corresponding target index.
    for i, char in enumerate(s):
        result[indices[i]] = char  # Place character at the correct position.
    
    # Join the list into a string and return it.
    return ''.join(result)

# Example usage:
# s = "codeleet", indices = [4,5,6,7,0,2,1,3]
# Output should be "leetcode"
← Back to All Questions