358. Rearrange String k Distance Apart
这道题就是把所有值都进行最大区分,在重新加入heap的时候要注意,如果两个值有同样的count,那么后访问过的要先加进去,比如说bba, size=1,先加入b,此时a,b的count都是1,这时候要先加入a,再加入b
class Solution(object):
def rearrangeString(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
if k == 0:
return s
h = {}
for c in s:
h[c] = h.get(c, 0) + 1
heap = []
for key, val in h.iteritems():
heapq.heappush(heap, [-val, key])
res = []
while heap:
temp = []
n = len(s) - len(res)
for _ in range(min(k, n)):
if not heap:
return ""
cur_val, key = heapq.heappop(heap)
res.append(key)
cur_val += 1
if cur_val != 0:
temp.append([cur_val, key])
while temp:
heapq.heappush(heap, temp.pop())
return "".join(res)
网友评论