Reorganize String

To rearrange the characters of the given string s so that no two adjacent characters are the same, we can follow these steps:

Count the Occurrences: Count the occurrences of each character in the string using a Counter.
Create a Max Heap: Put the characters into a max heap (priority queue), prioritizing by the number of occurrences.
Build the Result: Pop characters from the heap, and add them to the result string. Make sure not to put the same character adjacent to itself. If at any point this is not possible, return an empty string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import Counter
import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        counts = Counter(s)
        max_heap = [(-count, char) for char, count in counts.items()]
        heapq.heapify(max_heap)

        result = []
        prev_count, prev_char = 0, ''

        while max_heap:
            count, char = heapq.heappop(max_heap)
            result.append(char)
            if prev_count < 0:
                heapq.heappush(max_heap, (prev_count, prev_char))
            prev_count, prev_char = count + 1, char

        if len(result) != len(s):
            return ""

        return ''.join(result)

Example

s = "aab"
counts = {'a': 2, 'b': 1}
max_heap = [(-2, 'a'), (-1, 'b')]
result = ["a", "b", "a"]
output = "aba"

Insights

Efficiency: The time complexity of the algorithm is (O(n \log k)), where (n) is the length of the string s, and (k) is the number of distinct characters in the string. This is due to the use of a heap, which takes (O(\log k)) time for each operation.
Handling Adjacent Characters: By using a max heap, we ensure that the character with the most remaining occurrences is always considered first. By also keeping track of the previously used character, we can prevent it from being used again immediately, ensuring that no two adjacent characters are the same.
Edge Cases: If it is not possible to arrange the characters as required, the algorithm will detect this and return an empty string. This happens when there are too many occurrences of one character to be spread out among the other characters, such as in the example “aaab”.

Define the Terms

Define the Interface Input: string Output: string

Analyze the Input and Output

a ab aa aab => size is 3 aaa => return ’’ (if the frequency exceeds a certain size, it is NOT possible)

What is the size of the given string? What should be maximum length of the most frequently occuring letter to maintain the invariant?

Example 2: “aaab” violates the invariant, return ''

“aaab” => size = 4 letter a => 3 times

output ‘_x_x_x_x’ cannot exceed 4 for size 8 (2 * 4 - 1) < 8 ‘x_x_x’ cannot exceed 4 for size 7 (2 * 4 - 1) < 7

(2 * 5) - 1 = 9 > 8 (2 * 5) - 1 = 9 > 7

If 5 it will fail for size 8 If 5 it will fail for size 7

What is the relationship to express the invariant in the code? Impossible case is when we return ’’ ???

Identify the Invariants Two characters that are adjacent to each other are not the same.

Identify the constraints S will consist of lowercase letters and have length in range [1, 500]

Search the Problem Space

Classify the Problem

Is there any similar problem you have worked on before?
Task Scheduler (If we make the problem abstract by removing the OS context)

Analyze the Examples

Edge Case string with just one letter in it. Return that letter.

Solve the Problem by Hand

Interleaving the letters

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

Greedy Approach

Get the frequency of all the letters
Iterate through the highest frequency map
Sort by descending
Start constructing the output string
Is it possible to solve this problem in constant space?

Somehow interleave the repeating letter by finding the right slot for that letter.

What is this approach?

Greedy approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

Frequency counter by scanning the string
Check invariant to see if it is possible to construct if it is not possible, return '’
Highest frequency letter must be used and exhausted first

Key Takeaways

0 [2, 1]

‘aab’ [‘a’, ‘a’, ‘b’]

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
# @param {String} s
# @return {String}
def reorganize_string(s)
    counter = Array.new(26, 0)
    most_frequent = 0
    ascii = 0

    s.chars.each do |c|
       ascii = c.ord - 'a'.ord
        counter[ascii] += 1

        if counter[ascii] > counter[most_frequent]
            most_frequent = ascii
        end
    end

    if (2 * counter[most_frequent] - 1 > s.size)
        return ''
    end
#     _x_x_x_
    i = 0
    while(counter[most_frequent] != 0)
       s[i] = ('a'.ord + most_frequent).chr
       i += 2
       counter[most_frequent] -= 1 
    end

    for j in (0...26)
       while counter[j] != 0
          if i >= s.size 
            i = 1
          end
          s[i] = ('a'.ord + j).chr
          counter[j] -= 1
          i += 2
       end
    end

    return s
end

What is the relationship between the length of the string and whether it is possible to maintain the invariant or not?

Do we need to use frequency counter to keep track of the number of times a letter is repeating?

Is it possible to solve the problem in constant space?

@param {String} s

@return {String}

def reorganize_string(s) counter = Array.new(26, 0) most_frequent = 0 ascii = 0

s.chars.each do |c| ascii = c.ord - ‘a’.ord counter[ascii] += 1

if counter[ascii] > counter[most_frequent]
  most_frequent = ascii
end

end

if (2 * counter[most_frequent] - 1 > s.size) return ’’ end

What if the second most frequency prevents from forming

the string of given string? Why is this case not handled?

i = 0
while(counter[most_frequent] != 0)
  
  s[i] = ('a'.ord + most_frequent).chr
  p s
  
  i += 2
  counter[most_frequent] -= 1
end

for j in (0...26)
  while counter[j] != 0
    if i >= s.size
      i = 1
    end
    s[i] = ('a'.ord + j).chr
    counter[j] -= 1
    i += 2
  end
end

return s
end