Rearrange String K Distance Apart Problem LeetCode

Problem:

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:
str = "aabbcc", k = 3
Answer: "abcabc"
Explanation: The same letters are at least distance 3 from each other.

Example 2:
str = "aaabc", k = 3
Answer: ""
Explanation: It is not possible to rearrange the string.

Example 3:
str = "aaadbbcc", k = 2
Answer 1: "abacabcd"
Answer 2: Another possible answer is: "abcabcda"
Explanation: The same letters are at least distance 2 from each other.

HINTS:

• store character counts in hash
• sort the characters by frequency using max heap
• repeat while stack is not empty
• pop the max frequency element from heap, and repeat this min(k, s.length()) times
• build a string using the polled chars, if the frequency of chars >0 in map, store it in a separate arraylist and add them back to the heap

Solution: