Given a non-empty string s 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:

s = "aabbcc", k = 3Result: "abcabc"The same letters are at least distance 3 from each other.

 

Example 2:

s = "aaabc", k = 3 Answer: ""It is not possible to rearrange the string.

本题和task shceduler 一样的思路。

class Solution {    struct mycompare{        bool operator()(pair
     
      & p1, pair
      
       & p2){            if(p1.first == p2.first) return p1.second > p2.second;//字母升序            return p1.first < p2.first;//数字大小降序排列        }    };public:    string rearrangeString(string str, int k) {        if(k == 0) return str;        unordered_map
       
         dict;        for(char ch : str) dict[ch]++;        int left = (int)str.size();        priority_queue
        
         
          , vector
          
           
            >, mycompare > pq; for(auto it = dict.begin(); it != dict.end(); it++){ pq.push(make_pair(it->second, it->first)); } string res; while(!pq.empty()){ vector
            
             
              > cache; int count = min(k, left); for(int i = 0; i < count; i++){ if(pq.empty()) return ""; auto tmp = pq.top(); pq.pop(); res.push_back(tmp.second); if(--tmp.first > 0) cache.push_back(tmp); left--; } for(auto p : cache){ pq.push(p); } } return res; }};
             
            
           
          
         
        
       
      
     

 

 

Example 3:

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