Question

Formatted question description: https://leetcode.ca/all/358.html

358	Rearrange String k Distance Apart

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

Result: "abcabc"

The same letters are at least distance 3 from each other.

Example 2:

str = "aaabc", k = 3

It is not possible to rearrange the string.

Example 3:

str = "aaadbbcc", k = 2

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.



Algorithm

We need a hash table to establish the mapping between characters and their occurrences, and then a heap is needed to store each heap of mappings, sorted according to the number of occurrences.

Then if the heap is not empty, we start the loop. We find the smaller value between the length of k and str, and then traverse from 0 to this smaller value.

For each traversed value,

• if the heap is empty at this time, indicating that this position cannot be filled with characters, return an empty string,
• otherwise we take a pair of mappings from the top of the heap, and then add letters to the result, then the number of mappings is reduced by 1,
• if the number after subtracting 1 If it is still greater than 0, we add this mapping to the temporary set v, and at the same time the number of str len is reduced by 1.

After traversing once, we add the mapping pairs in the temporary set to the heap.

Java