Reorganize a String
Heaps: lesson 6 of 7
Spend the commonest letter first, and hold it back one round.
Lesson 6 of 7 · 6 min
Reorganize a String
Step 1 of 8
Six letters, two of each. No two neighbours may match, so the commonest remaining letter always goes next.
The Idea
No two neighbours may match. The greedy choice is to place whichever letter has the most copies left, because that is the one at risk of piling up at the end.
Keep the letter you just used out of the heap for exactly one round. If the heap empties before the string is filled, no arrangement exists.
Real-World Example
Seating a wedding table so no two people from the same family sit together. You place the largest family first and skip them for one chair — leave them until last and the final seats are all cousins.
The Code
import heapq
from collections import Counter
def reorganize(s):
heap = [(-n, ch) for ch, n in Counter(s).items()]
heapq.heapify(heap) # commonest letter on top
out, held = [], None
while heap:
n, ch = heapq.heappop(heap) # never the letter placed last round
out.append(ch)
if held: heapq.heappush(heap, held) # that one is legal again now
held = (n + 1, ch) if n + 1 else None
return "".join(out) if len(out) == len(s) else ""
print(reorganize("aabbcc")) # abcabc
print(reorganize("aaab")) # "" -- one letter is too common to spread outYour turn
Put the steps in the right order.
- Push the letter held back from the previous round, now that it is legal again
- Count the letters and build a heap ordered by count, largest first
- Hold this letter back with its count reduced by one
- Pop the top letter and append it to the output
Mini quiz
1 / 3