101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Frequency Count and Check Approach - Complex approach
  2. Max Heap Approach - Complex approach
  3. Alternating Positions Approach - Complex approach

Approach 1: Frequency Count and Check Approach

Let's start by understanding the problem: we need to rearrange the characters in a string so that no two adjacent characters are the same. If this is not possible, we return an empty string.

Thinking Process: The first step is to determine if it's even possible to rearrange the string as required. If a character appears too frequently, it will inevitably end up adjacent to itself in any arrangement.

Specifically, if a character appears more than (n+1)/2 times (where n is the length of the string), it's impossible to avoid having that character adjacent to itself. This is because even if we place this character at alternate positions, it will still need more than half the positions in the string.

Intuition: After checking if a valid rearrangement is possible, we need to actually construct it. One approach is to sort the characters by their frequency (most frequent first) and then place them in the string. However, simply placing them sequentially won't work. Instead, we can place characters at alternate positions (first all even positions, then all odd positions) to ensure no two identical characters are adjacent.

Algorithm:

  1. Count the frequency of each character in the string.
  2. Check if any character appears more than (n+1)/2 times. If so, return an empty string.
  3. Sort the characters by their frequency (most frequent first).
  4. Place the characters in the result string, starting with even indices (0, 2, 4, ...) and then moving to odd indices (1, 3, 5, ...).
  5. Return the rearranged string.

Time Complexity:

O(n log k)

Where n is the length of the string and k is the number of unique characters. Counting frequencies takes O(n) time. Sorting characters by frequency takes O(k log k) time. Constructing the result string takes O(n) time. Since k is at most 26 (for lowercase English letters), the sorting step is effectively O(1), making the overall time complexity O(n).

Space Complexity:

O(n)

We need O(k) space to store the frequency counts and O(n) space to store the result string. Since k is at most 26, the space complexity is dominated by the result string, making it O(n).

Approach 2: Max Heap Approach

Another approach is to use a max heap (priority queue) to efficiently track and extract characters by their frequency.

Thinking Process: After counting the frequencies and checking if a valid rearrangement is possible, we can use a max heap to always extract the most frequent remaining character. This allows us to greedily construct the result string.

To avoid placing the same character adjacent to itself, we can temporarily set aside the character we just used and reinsert it into the heap after placing a different character. This ensures that we always alternate between different characters.

Intuition: The max heap approach is more elegant than the sorting approach because it naturally gives us the most frequent character at each step. By temporarily setting aside the character we just used, we ensure that we never place the same character adjacent to itself.

Algorithm:

  1. Count the frequency of each character in the string.
  2. Check if any character appears more than (n+1)/2 times. If so, return an empty string.
  3. Create a max heap and add all characters with their frequencies.
  4. While the heap is not empty:
  5. a. Extract the most frequent character from the heap.
  6. b. Append it to the result string.
  7. c. Decrease its frequency by 1.
  8. d. If there was a character set aside from the previous iteration, add it back to the heap.
  9. e. If the current character still has remaining occurrences, set it aside for the next iteration.
  10. Return the rearranged string.

Time Complexity:

O(n log k)

Where n is the length of the string and k is the number of unique characters. Counting frequencies takes O(n) time. Each heap operation takes O(log k) time, and we perform O(n) such operations. Since k is at most 26, the heap operations are effectively O(1), making the overall time complexity O(n).

Space Complexity:

O(n)

We need O(k) space to store the frequency counts and the heap, and O(n) space to store the result string. Since k is at most 26, the space complexity is dominated by the result string, making it O(n).

Approach 3: Alternating Positions Approach

A more direct approach is to place characters at alternating positions in the result string.

Thinking Process: After counting the frequencies and checking if a valid rearrangement is possible, we can sort the characters by their frequency (most frequent first). Then, we place them in the result string at alternating positions.

Specifically, we first fill all even positions (0, 2, 4, ...) with the most frequent characters, and then fill all odd positions (1, 3, 5, ...) with the remaining characters. This ensures that no two identical characters are adjacent.

Intuition: By placing characters at alternating positions, we ensure that characters of the same type are separated by at least one other character. This approach is particularly elegant because it directly constructs the result string without needing to check for adjacency at each step.

Algorithm:

  1. Count the frequency of each character in the string.
  2. Check if any character appears more than (n+1)/2 times. If so, return an empty string.
  3. Sort the characters by their frequency (most frequent first).
  4. Initialize an empty result string of the same length as the input string.
  5. Place characters at even positions (0, 2, 4, ...) in the result string, starting with the most frequent character.
  6. When all even positions are filled, continue placing characters at odd positions (1, 3, 5, ...).
  7. Return the rearranged string.

Time Complexity:

O(n log k)

Where n is the length of the string and k is the number of unique characters. Counting frequencies takes O(n) time. Sorting characters by frequency takes O(k log k) time. Constructing the result string takes O(n) time. Since k is at most 26, the sorting step is effectively O(1), making the overall time complexity O(n).

Space Complexity:

O(n)

We need O(k) space to store the frequency counts and O(n) space to store the result string. Since k is at most 26, the space complexity is dominated by the result string, making it O(n).

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function reorganizeString(s):
    // Count the frequency of each character
    freq = new Map()
    for each character c in s:
        freq[c] = freq[c] + 1 or 1
    
    // Check if a valid rearrangement is possible
    maxFreq = maximum value in freq
    if maxFreq > (s.length + 1) / 2:
        return ""
    
    // Sort characters by frequency (most frequent first)
    chars = sort keys of freq by their values in descending order
    
    // Place characters at alternate positions
    result = new array of length s.length
    index = 0
    
    // Place characters at even positions
    for each character c in chars:
        for i from 1 to freq[c]:
            result[index] = c
            index += 2
            if index >= s.length:
                index = 1  // Switch to odd positions
    
    return result as a string
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone