Jobs

Interviews

Discussions

Reorganize String

Medium

Roblox

0 views

Topics:

Greedy AlgorithmsArrays

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

Reorganize String

Medium

Roblox

0 views

Topics:

Greedy AlgorithmsArrays

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

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 expected behavior if the input string is null or empty?
Are there any restrictions on the characters in the input string (e.g., only lowercase letters)?
If it's impossible to reorganize the string such that no adjacent characters are the same, what should I return? An empty string, null, or throw an exception?
If there are multiple valid reorganizations, is any one acceptable, or is there a specific one I should aim for (e.g., lexicographically smallest)?
What is the maximum length of the input string?

Brute Force Solution

Approach

The brute force method for reorganizing a string involves trying every single possible arrangement of the letters. We check each arrangement to see if it meets the requirement that no two adjacent letters are the same. If an arrangement works, we return it; otherwise, we keep trying different arrangements.

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

Generate all possible arrangements (permutations) of the letters in the string.
For each arrangement, check if any two neighboring letters are identical.
If you find an arrangement where no two neighbors are the same, that's your answer, so stop and return that arrangement.
If you go through all possible arrangements and none of them work (meaning they all have repeated neighbors), then there is no valid reorganization, so return an indication of failure.

Code Implementation

def reorganize_string_brute_force(input_string):
    import itertools

    all_permutations = itertools.permutations(input_string)

    for permutation in all_permutations:
        string_permutation = ''.join(permutation)

        # Check for adjacent identical characters

        is_valid = True
        for index in range(len(string_permutation) - 1):
            if string_permutation[index] == string_permutation[index + 1]:
                is_valid = False
                break

        # Return current string if valid
        if is_valid:
            return string_permutation

    # If no valid string found return empty
    return ""

Big(O) Analysis

Time Complexity

O(n! * n) – The described brute force approach first generates all possible permutations of the input string of length n. Generating all permutations takes O(n!) time. For each of these n! permutations, we iterate through the string of length n to check if any adjacent characters are the same. This check takes O(n) time. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The dominant space complexity comes from generating all possible permutations of the input string, where N is the length of the string. Storing all N! permutations requires significant auxiliary space. Specifically, to store even a single permutation of length N, we need an array of size N. However, since the algorithm generates all possible permutations simultaneously (conceptually), the total auxiliary space grows proportional to N!, making the space complexity O(N!).

Optimal Solution

Approach

To rearrange a string so that no two identical characters are next to each other, we focus on distributing the most frequent characters first. This prevents having a large cluster of identical characters that are impossible to separate. The main idea is to prioritize characters based on their frequency to create a valid arrangement.

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

First, count how many times each character appears in the string.
Identify the character that appears most frequently.
Start building the rearranged string by placing the most frequent character at every other position.
Then, take the next most frequent character and place it in the empty positions.
Continue this process with all the remaining characters, placing them in the empty spaces based on their frequency.
If at any point you run out of spaces before using all of a character, it means a valid arrangement is not possible, and you should indicate that.
If you successfully place all characters, you have created the rearranged string.

Code Implementation

def reorganize_string(input_string):
    character_counts = {}
    for char in input_string:
        character_counts[char] = character_counts.get(char, 0) + 1

    sorted_characters = sorted(character_counts.items(), key=lambda item: item[1], reverse=True)

    reorganized_string = [''] * len(input_string)
    index = 0

    # Distribute most frequent characters first
    for char, count in sorted_characters:
        for _ in range(count):
            if index >= len(input_string):
                index = 1

            # If no valid arrangement is possible
            if index >= len(input_string):
                return ""

            reorganized_string[index] = char
            index += 2

    return ''.join(reorganized_string)

Big(O) Analysis

Time Complexity

O(n log n) – Counting character frequencies involves iterating through the string of length n, taking O(n) time. Prioritizing characters based on frequency typically uses a heap-based priority queue. Inserting each of the up to n distinct characters into the heap takes O(log n) time, and we do this up to n times resulting in O(n log n) for heap operations. Building the reorganized string involves placing each of the n characters at the correct index. Thus, the dominant operation is the heap operations resulting in a time complexity of O(n log n).

Space Complexity

O(1) – The algorithm uses a character frequency count, which, assuming a fixed character set (e.g., ASCII), requires constant space. The rearranged string is built in-place (or implicitly using a fixed-size output buffer), so it doesn't contribute to auxiliary space. Therefore, the space complexity remains constant regardless of the input string length, N.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or handle as an invalid input by throwing an exception.
String with only one character	Return the original single-character string as it's already reorganized.
String where one character's count is more than (n+1)/2	Return an empty string since a valid reorganization is impossible in this case.
String with all identical characters	Return an empty string as it's impossible to reorganize such a string.
Very long input string (performance)	Ensure the solution uses an efficient data structure (e.g., priority queue) to avoid quadratic time complexity.
String with only two distinct characters	If their counts differ by more than one, return an empty string, otherwise reorganize them alternatingly.
String with a balanced character distribution (close to equal counts)	Ensure the algorithm correctly interleaves the characters even when the counts are very similar.
String with Unicode characters	The character counting mechanism must correctly handle extended character sets beyond basic ASCII.

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 expected behavior if the input string is null or empty?
Are there any restrictions on the characters in the input string (e.g., only lowercase letters)?
If it's impossible to reorganize the string such that no adjacent characters are the same, what should I return? An empty string, null, or throw an exception?
If there are multiple valid reorganizations, is any one acceptable, or is there a specific one I should aim for (e.g., lexicographically smallest)?
What is the maximum length of the input string?

Brute Force Solution

Approach

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

Generate all possible arrangements (permutations) of the letters in the string.
For each arrangement, check if any two neighboring letters are identical.
If you find an arrangement where no two neighbors are the same, that's your answer, so stop and return that arrangement.
If you go through all possible arrangements and none of them work (meaning they all have repeated neighbors), then there is no valid reorganization, so return an indication of failure.

Code Implementation

def reorganize_string_brute_force(input_string):
    import itertools

    all_permutations = itertools.permutations(input_string)

    for permutation in all_permutations:
        string_permutation = ''.join(permutation)

        # Check for adjacent identical characters

        is_valid = True
        for index in range(len(string_permutation) - 1):
            if string_permutation[index] == string_permutation[index + 1]:
                is_valid = False
                break

        # Return current string if valid
        if is_valid:
            return string_permutation

    # If no valid string found return empty
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many times each character appears in the string.
Identify the character that appears most frequently.
Start building the rearranged string by placing the most frequent character at every other position.
Then, take the next most frequent character and place it in the empty positions.
Continue this process with all the remaining characters, placing them in the empty spaces based on their frequency.
If at any point you run out of spaces before using all of a character, it means a valid arrangement is not possible, and you should indicate that.
If you successfully place all characters, you have created the rearranged string.

Code Implementation

def reorganize_string(input_string):
    character_counts = {}
    for char in input_string:
        character_counts[char] = character_counts.get(char, 0) + 1

    sorted_characters = sorted(character_counts.items(), key=lambda item: item[1], reverse=True)

    reorganized_string = [''] * len(input_string)
    index = 0

    # Distribute most frequent characters first
    for char, count in sorted_characters:
        for _ in range(count):
            if index >= len(input_string):
                index = 1

            # If no valid arrangement is possible
            if index >= len(input_string):
                return ""

            reorganized_string[index] = char
            index += 2

    return ''.join(reorganized_string)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or handle as an invalid input by throwing an exception.
String with only one character	Return the original single-character string as it's already reorganized.
String where one character's count is more than (n+1)/2	Return an empty string since a valid reorganization is impossible in this case.
String with all identical characters	Return an empty string as it's impossible to reorganize such a string.
Very long input string (performance)	Ensure the solution uses an efficient data structure (e.g., priority queue) to avoid quadratic time complexity.
String with only two distinct characters	If their counts differ by more than one, return an empty string, otherwise reorganize them alternatingly.
String with a balanced character distribution (close to equal counts)	Ensure the algorithm correctly interleaves the characters even when the counts are very similar.
String with Unicode characters	The character counting mechanism must correctly handle extended character sets beyond basic ASCII.