Problem Description

You are given a string s consisting of characters. Your task is to rearrange the characters in the string such that no two adjacent characters are the same.

The goal is to find any valid rearrangement where consecutive characters are different. If it's impossible to create such an arrangement, return an empty string "".

For example:

• If s = "aab", you could rearrange it to "aba" where no adjacent characters are identical
• If s = "aaab", no valid rearrangement exists since you have too many 'a's to separate them all, so you would return ""

The key challenge is determining when a rearrangement is possible and then constructing a valid arrangement when it exists. A rearrangement becomes impossible when any single character appears too frequently to be separated by other characters.

Intuition

To avoid having adjacent characters be the same, we need to spread out the characters as much as possible. Think of it like placing items on a shelf where identical items can't be next to each other.

The first key insight is determining when it's impossible to create a valid arrangement. If any character appears more than (n + 1) // 2 times (where n is the string length), it's impossible to separate all occurrences. For example, in a string of length 5, if a character appears 4 times, we can't arrange them without having at least two adjacent occurrences.

The second insight is about the placement strategy. To maximize separation between identical characters, we can use an alternating pattern - place characters at positions 0, 2, 4, 6... (even indices) first, then fill positions 1, 3, 5, 7... (odd indices). This creates maximum spacing between identical characters.

Why start with the most frequent characters? By placing the most frequent characters first using this alternating pattern, we ensure they get the maximum possible separation. If we placed less frequent characters first, we might run out of "good" positions for the more frequent ones.

The alternating placement works because:

• When we place a character at even indices (0, 2, 4...), all occurrences are separated by at least one position
• Once we run out of even indices, we switch to odd indices (1, 3, 5...)
• This ensures that characters placed at even positions never touch characters at odd positions of the same type

This greedy approach of handling the most frequent characters first with alternating placement guarantees that if a valid arrangement exists, we'll find it.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows the intuition of alternating placement with a greedy approach:

1. Count character frequencies: Use a Counter to count occurrences of each character in the string. This gives us cnt where cnt[char] is the frequency of that character.

2. Check validity: Find the maximum frequency among all characters with mx = max(cnt.values()). If mx > (n + 1) // 2, return an empty string since it's impossible to arrange the characters without adjacency.

3. Initialize the result array: Create an array ans of size n to build our rearranged string. Using an array allows O(1) access to any position.

4. Sort by frequency: Use cnt.most_common() to get characters sorted by their frequency in descending order. This ensures we place the most frequent characters first.

5. Alternating placement algorithm:

   • Start with index i = 0 (first even position)
   • For each character k with frequency v:
     • Place the character at position i
     • Decrement the frequency: v -= 1
     • Move to the next even position: i += 2
     • When we exceed the array bounds (i >= n), switch to odd positions by setting i = 1

   This creates the pattern: positions 0, 2, 4, 6... then 1, 3, 5, 7...

6. Build the result: After filling all positions, join the array into a string with ''.join(ans).

The time complexity is O(n log k) where k is the number of unique characters (for sorting), and space complexity is O(n) for the result array. The alternating index pattern guarantees that identical characters are maximally separated, preventing any adjacent duplicates if a valid arrangement exists.

Example Walkthrough

Let's walk through the solution with s = "aaabbc":

Step 1: Count character frequencies

• 'a': 3 occurrences
• 'b': 2 occurrences
• 'c': 1 occurrence
• String length n = 6

Step 2: Check validity

• Maximum frequency = 3 (from 'a')
• Check: 3 ≤ (6 + 1) // 2 = 3 ✓
• Valid arrangement is possible!

Step 3: Initialize result array

• ans = [_, _, _, _, _, _] (6 empty positions)

Step 4: Sort characters by frequency (descending)

• Order: 'a'(3), 'b'(2), 'c'(1)

Step 5: Place characters using alternating pattern

Start with i = 0 (even positions first):

• Place 'a' (3 times):

  • Place 'a' at position 0: ans = [a, _, _, _, _, _], i = 2
  • Place 'a' at position 2: ans = [a, _, a, _, _, _], i = 4
  • Place 'a' at position 4: ans = [a, _, a, _, a, _], i = 6
  • i = 6 ≥ n, so switch to odd positions: i = 1

• Place 'b' (2 times):

  • Place 'b' at position 1: ans = [a, b, a, _, a, _], i = 3
  • Place 'b' at position 3: ans = [a, b, a, b, a, _], i = 5

• Place 'c' (1 time):

  • Place 'c' at position 5: ans = [a, b, a, b, a, c], i = 7

Step 6: Build final result

• Join array: "ababac"

The final string "ababac" has no adjacent identical characters! The alternating placement pattern ensured that the most frequent character 'a' was maximally spread out at positions 0, 2, and 4, while other characters filled the gaps.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log k) where n is the length of the string and k is the number of unique characters (at most 26 for lowercase English letters).

• Creating the Counter takes O(n) time to count all characters
• Finding the maximum value from the counter takes O(k) time
• The most_common() method sorts the counter items, which takes O(k log k) time
• The nested while loop iterates through all characters exactly once, placing each character in the result array, which takes O(n) time total
• The final join operation takes O(n) time

Overall: O(n) + O(k) + O(k log k) + O(n) + O(n) = O(n + k log k). Since k ≤ 26 for lowercase letters and k ≤ n, this simplifies to O(n log k) or effectively O(n) when considering only lowercase English letters.

Space Complexity: O(n)

• The Counter object stores at most k key-value pairs, which takes O(k) space
• The answer array ans of size n takes O(n) space
• The final string created by join takes O(n) space

Overall: O(k) + O(n) + O(n) = O(n) since k ≤ n and the answer array dominates the space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Validity Check Formula

A frequent mistake is using the wrong formula to check if reorganization is possible. Developers often write:

• if max_frequency > n // 2: (incorrect)
• if max_frequency >= (n + 1) // 2: (incorrect)

The correct formula is if max_frequency > (n + 1) // 2:. This accounts for both even and odd length strings:

• For even length (n=4): A character can appear at most 2 times
• For odd length (n=5): A character can appear at most 3 times

Solution: Always use (n + 1) // 2 as the threshold. This ceiling division ensures correct validation for both even and odd string lengths.

2. Not Handling the Index Reset Properly

When filling positions alternately, developers might reset the index incorrectly:

# Wrong approach
current_index += 2
if current_index > string_length:  # Should be >= not >
    current_index = 1

This off-by-one error can cause index out of bounds or skip valid positions.

Solution: Check if current_index >= string_length to ensure you switch to odd indices at the right time.

3. Processing Characters in Wrong Order

Some implementations process characters randomly or in alphabetical order rather than by frequency:

# Wrong approach
for character in char_frequency:  # Processes in arbitrary order
    # Place character...

This can lead to invalid arrangements even when valid ones exist, especially when the most frequent character needs maximum spreading.

Solution: Always use char_frequency.most_common() to process characters in descending frequency order. This ensures the most constrained characters (highest frequency) get optimal placement first.

4. Modifying Counter While Iterating

Attempting to modify the frequency counter while iterating over it:

# Wrong approach
for character, frequency in char_frequency.most_common():
    result[current_index] = character
    char_frequency[character] -= 1  # Modifying original counter

Solution: Use a local variable to track remaining frequency within the loop, as shown in the correct implementation with while frequency > 0: frequency -= 1.

5. Using String Concatenation Instead of Array

Building the result using string concatenation:

# Inefficient approach
result = ""
# ... placement logic ...
result += character  # O(n) operation each time

This creates O(n²) time complexity due to string immutability in Python.

Solution: Use a list/array for O(1) position assignments, then join at the end with ''.join(result) for O(n) overall string construction.