More patterns for coding interviews |||

9- Rearrange string k distance apart

This pattern solves problems where you need to reorganize a string/number such that at least there are k characters (inclusive) between instances of the same character.

class Solution:
def reorganizeString(self, s):
queue, stack, ans =[(-count,char) for char, count in Counter(s).items()], [], ""
heapify(queue)

while queue:
for _ in range(2):
if not queue and stack: return ""
if queue:
count, char = heappop(queue)
ans += char
if count<-1: stack.append((count+1, char))

while stack: heappush(queue, stack.pop())

return ans
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
time, queue, stack = 0, [(-1*count, char) for char, count in Counter(tasks).items()], []
heapify(queue)

while queue:
for _ in range(n+1):
if queue or stack: time += 1
if queue:
count, char = heappop(queue)
if count<-1: stack.append((count+1,char))

while stack: heappush(queue, stack.pop())

return time
class Solution:
def rearrangeString(self, s, k):
queue, stack, ans =[(-count,char) for char, count in Counter(s).items()], [], ""
heapify(queue)

while queue:
for _ in range(k):
if not queue and stack: return ""
if queue:
count, char = heappop(queue)
ans += char
if count<-1: stack.append((count+1, char))

while stack: heappush(queue, stack.pop())

return ans

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store