[LeetCode] Rearrange String k Distance Apart 按距離為k隔離重排字元串

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 <code>""</code>.

Example 1:

Example 2:

Example 3:

Credits:

這道題給了我們一個字元串str，和一個整數k，讓我們對字元串str重新排序，使得其中相同的字元之間的距離不小于k，這道題的難度标為Hard，看來不是省油的燈。的确，這道題的解法用到了哈希表，堆，和貪婪算法。這道題我最開始想的算法沒有通過OJ的大集合逾時了，下面的方法是參考網上大神的解法，發現十分的巧妙。我們需要一個哈希表來建立字元和其出現次數之間的映射，然後需要一個堆來儲存這每一堆映射，按照出現次數來排序。然後如果堆不為空我們就開始循環，我們找出k和str長度之間的較小值，然後從0周遊到這個較小值，對于每個周遊到的值，如果此時堆為空了，說明此位置沒法填入字元了，傳回空字元串，否則我們從堆頂取出一對映射，然後把字母加入結果res中，此時映射的個數減1，如果減1後的個數仍大于0，則我們将此映射加入臨時集合v中，同時str的個數len減1，周遊完一次，我們把臨時集合中的映射對由加入堆中，參見代碼如下：