# More patterns for coding interviews |||

--

Unpopular patterns that show up often in coding interviews

Today I will share one pattern only.

I just came up with this implementation pattern today after knowing from a colleague that Leetcode 767. Reorganize String showed up in her phone interview today with Google. let’s dive right into it

# 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.

**The algorithm (Greedy): **

- Push unique characters, sorted by frequency, k times, while reducing the count of each character you push.

- Repeat the above step until you exhaust the count of all characters.

**The implementation approach:**

- Count the characters and heapify them in a max heap such that the max frequency character is at the top of the heap

- Pop most frequent character (the top of the heap) k times. while storing the poped elements in a stack

- For elements in the stack, reduce their count by one and push elements with count>0 to the heap again

- Repeat until you empty the queue and the stack.

Examples:

767. Reorganize String(Google)

`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

358. Rearrange String k Distance Apart

`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

That’s it for today.

Clap and follow for more patterns