Jobs

Interviews

Discussions

Shuffle String

Easy

Google

2 views

Topics:

ArraysStrings

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

Return the shuffled string.

For example:

If s = "codeleet", and indices = [4,5,6,7,0,2,1,3], the expected output is "leetcode". Here, the character at index 0 ('c') moves to index 4, the character at index 1 ('o') moves to index 5, and so on.
If s = "abc", and indices = [0,1,2], the expected output is "abc". In this case, each character remains in its original position after shuffling.

Write a function that takes the string s and the integer array indices as input and returns the shuffled string. Consider edge cases such as an empty string or a single-character string. What is the time and space complexity of your solution?

Shuffle String

Easy

Google

2 views

Topics:

ArraysStrings

Return the shuffled string.

For example:

If s = "codeleet", and indices = [4,5,6,7,0,2,1,3], the expected output is "leetcode". Here, the character at index 0 ('c') moves to index 4, the character at index 1 ('o') moves to index 5, and so on.
If s = "abc", and indices = [0,1,2], the expected output is "abc". In this case, each character remains in its original position after shuffling.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the `indices` array and the `s` string, and what are the size limits or constraints for both?
Is the `indices` array guaranteed to be the same length as the input string `s`?
Are all values in the `indices` array guaranteed to be within the valid index range for the string `s` (i.e., between 0 and length of `s` minus 1)?
Is the `indices` array guaranteed to contain a permutation of the numbers from 0 to n-1, where n is the length of the string?
If the input string `s` is empty, or if `indices` is empty, what should the function return?

Brute Force Solution

Approach

The brute force method for shuffling a string involves trying out every single possible arrangement of the characters within that string. We explore all combinations until we stumble upon the one that matches the specific requirements we're looking for. It's like trying every possible lock combination until the lock opens.

Here's how the algorithm would work step-by-step:

Start by listing all the different ways you can order the characters of the string.
For each of these orderings, check if it matches the desired target positions that are specified.
If an arrangement matches the desired arrangement, then we have found the solution.
If after checking every possible ordering, none match the target positions, there is no solution for the given input.

Code Implementation

def shuffle_string_brute_force(input_string, indices):
    import itertools

    number_of_characters = len(input_string)

    # Generate all possible permutations of indices
    all_permutations = itertools.permutations(range(number_of_characters))

    for permutation in all_permutations:

        shuffled_string = [''] * number_of_characters
        # Build the shuffled string based on the current permutation
        for index_position in range(number_of_characters):
            shuffled_string[indices[index_position]] = input_string[permutation[index_position]]

        # Check if this permutation matches the desired arrangement
        if ''.join(shuffled_string) == ''.join([input_string[i] for i in sorted(range(len(indices)), key=lambda k: indices[k])]):
            return ''.join(shuffled_string)

    # No matching permutation found.
    return ""

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force solution involves generating all possible permutations of the input string. For a string of length n, there are n! (n factorial) possible permutations. For each of these permutations, we need to iterate through the string of length n to check if it matches the desired target positions specified in the indices array. Therefore, the total time complexity is approximately n! multiplied by n, leading to O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all permutations of the input string. Storing these permutations requires space. In the worst case, we may need to store all N! permutations before finding a match or exhausting all possibilities, where N is the length of the string. Therefore, the auxiliary space complexity is proportional to the number of permutations, or N!.

Optimal Solution

Approach

The goal is to rearrange a string according to a given set of instructions. Instead of moving characters one at a time, we directly place each character into its correct final position all at once.

Here's how the algorithm would work step-by-step:

Create a new string that is the same size as the original string. This will be where we put the reordered characters.
Go through the list of instructions, which tells you where each character from the original string needs to move to.
For each character in the original string, use its corresponding instruction to put it into the correct location in the new string.
Once you have placed all the characters based on the instructions, the new string will be the answer.

Code Implementation

def shuffle_string(input_string, indices):
    string_length = len(input_string)
    # Initialize the shuffled string with the correct size.
    shuffled_string = [''] * string_length

    for index, character in enumerate(input_string):
        # Place each character at its designated index.
        destination_index = indices[index]
        shuffled_string[destination_index] = character

    # Construct the final shuffled string
    return ''.join(shuffled_string)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once to place each character into its correct position in the new string. The indices array, also of length n, guides this placement. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n) time complexity. The string creation is also proportional to n, but this is also a single iteration.

Space Complexity

O(N) – The algorithm creates a new string that is the same size as the original string to store the reordered characters. The size of this new string is directly proportional to the length of the original string, denoted as N. Therefore, the auxiliary space required is N. Other than the output string, the operations do not create other data structures that depend on the input string's size, so the total space used approximates to O(N).

Edge Cases

Case	How to Handle
Null or empty string for s	Return an empty string or throw an IllegalArgumentException as appropriate.
Null or empty array for indices	Return an empty string or throw an IllegalArgumentException as appropriate.
String 's' and 'indices' array have different lengths	Throw an IllegalArgumentException since shuffling is not possible.
Indices array contains out-of-bounds indices (negative or greater than or equal to length of s)	Throw an IllegalArgumentException, indicating invalid index mapping.
Indices array contains duplicate indices	Throw an IllegalArgumentException as this would overwrite values.
String 's' contains Unicode characters.	The algorithm should correctly handle Unicode characters as Java strings are UTF-16 encoded.
Maximum string length	Ensure the StringBuilder or char array used to build the shuffled string has sufficient capacity to avoid memory issues.
Integer overflow in index calculations	Indices should be validated to ensure they don't cause any potential integer overflows during the mapping process.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the `indices` array and the `s` string, and what are the size limits or constraints for both?
Is the `indices` array guaranteed to be the same length as the input string `s`?
Are all values in the `indices` array guaranteed to be within the valid index range for the string `s` (i.e., between 0 and length of `s` minus 1)?
Is the `indices` array guaranteed to contain a permutation of the numbers from 0 to n-1, where n is the length of the string?
If the input string `s` is empty, or if `indices` is empty, what should the function return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by listing all the different ways you can order the characters of the string.
For each of these orderings, check if it matches the desired target positions that are specified.
If an arrangement matches the desired arrangement, then we have found the solution.
If after checking every possible ordering, none match the target positions, there is no solution for the given input.

Code Implementation

def shuffle_string_brute_force(input_string, indices):
    import itertools

    number_of_characters = len(input_string)

    # Generate all possible permutations of indices
    all_permutations = itertools.permutations(range(number_of_characters))

    for permutation in all_permutations:

        shuffled_string = [''] * number_of_characters
        # Build the shuffled string based on the current permutation
        for index_position in range(number_of_characters):
            shuffled_string[indices[index_position]] = input_string[permutation[index_position]]

        # Check if this permutation matches the desired arrangement
        if ''.join(shuffled_string) == ''.join([input_string[i] for i in sorted(range(len(indices)), key=lambda k: indices[k])]):
            return ''.join(shuffled_string)

    # No matching permutation found.
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to rearrange a string according to a given set of instructions. Instead of moving characters one at a time, we directly place each character into its correct final position all at once.

Here's how the algorithm would work step-by-step:

Create a new string that is the same size as the original string. This will be where we put the reordered characters.
Go through the list of instructions, which tells you where each character from the original string needs to move to.
For each character in the original string, use its corresponding instruction to put it into the correct location in the new string.
Once you have placed all the characters based on the instructions, the new string will be the answer.

Code Implementation

def shuffle_string(input_string, indices):
    string_length = len(input_string)
    # Initialize the shuffled string with the correct size.
    shuffled_string = [''] * string_length

    for index, character in enumerate(input_string):
        # Place each character at its designated index.
        destination_index = indices[index]
        shuffled_string[destination_index] = character

    # Construct the final shuffled string
    return ''.join(shuffled_string)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string for s	Return an empty string or throw an IllegalArgumentException as appropriate.
Null or empty array for indices	Return an empty string or throw an IllegalArgumentException as appropriate.
String 's' and 'indices' array have different lengths	Throw an IllegalArgumentException since shuffling is not possible.
Indices array contains out-of-bounds indices (negative or greater than or equal to length of s)	Throw an IllegalArgumentException, indicating invalid index mapping.
Indices array contains duplicate indices	Throw an IllegalArgumentException as this would overwrite values.
String 's' contains Unicode characters.	The algorithm should correctly handle Unicode characters as Java strings are UTF-16 encoded.
Maximum string length	Ensure the StringBuilder or char array used to build the shuffled string has sufficient capacity to avoid memory issues.
Integer overflow in index calculations	Indices should be validated to ensure they don't cause any potential integer overflows during the mapping process.