-
Notifications
You must be signed in to change notification settings - Fork 0
/
231.py
39 lines (31 loc) · 1007 Bytes
/
231.py
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
# This problem was asked by IBM.
# Given a string with repeated characters, rearrange the string so that no two adjacent
# characters are the same. If this is not possible, return None.
# For example, given "aaabbc", you could return "ababac". Given "aaab", return None.
####
import heapq
def string_nonrep(rep_str):
char_count = {}
for c in rep_str:
char_count[c] = char_count.get(c, 0) + 1
# max heap emulation
pq = []
for k, v in char_count.items():
heapq.heappush(pq, (-v, k))
ret = ""
# placeholder element
prev = (1, -1)
while True:
prio, c = heapq.heappop(pq)
# if placeholder element is reached, break
if prio == 1:
break
ret += c
# insert prev back into heap
if prev[0] != 0:
heapq.heappush(pq, prev)
prev = (prio+1, c)
return ret if len(ret) == len(rep_str) else None
####
print(string_nonrep("aaabbc"))
print(string_nonrep("aaab"))