[Solved] Given the following Python code implementing the max heap app... Given the following Python code implementing the max heap approach to reorganize a string, what is the output when the input is "aab"? | Greedy Algorithms

Greedy Algorithms - Reorganize String (No Two Adjacent Same)

Given the following Python code implementing the max heap approach to reorganize a string, what is the output when the input is "aab"?

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(max_heap)
    prev_count, prev_char = 0, ''
    result = []

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

    res_str = ''.join(result)
    if len(res_str) != len(s):
        return ""
    return res_str

print(reorganizeString("aab"))

A"baa"

B"aab"

C"aba"

D"" (empty string)

Step-by-Step Solution

Solution:

Step 1: Trace first iteration
Heap contains [(' -2', 'a'), ('-1', 'b')]. Pop (-2, 'a'), append 'a', prev_count= -1, prev_char='a'.
Step 2: Trace second iteration
Pop (-1, 'b'), append 'b', push back (-1, 'a') since prev_count < 0, update prev_count=0, prev_char='b'. Next pop (-1, 'a'), append 'a'. Result is "aba".
Final Answer:
Option C -> Option C
Quick Check:
Output "aba" has no two adjacent same chars and uses all letters [OK]

Quick Trick: Trace heap pops and pushes carefully [OK]

Common Mistakes:

MISTAKES

Returning input unchanged
Appending characters without heap pushback
Off-by-one in count update

Trap Explanation:

PITFALL

Candidates often forget to push back previous char or miscount frequency updates, leading to wrong output.

Interviewer Note:

CONTEXT

Tests ability to mentally execute heap-based greedy code and track variables.

Master "Reorganize String (No Two Adjacent Same)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Greedy Algorithms Quizzes

Given the following Python code implementing the max heap approach to reorganize a string, what is the output when the input is "aab"?

Step 1: Trace first iteration

Step 2: Trace second iteration

Final Answer:

Quick Check:

Want More Practice?