# More patterns for coding interviews |||

Unpopular patterns that show up often in coding interviews

Series: Part1, Part2

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:

`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`