C++ O(n) time, 24lines


  • 0
    S
    class Solution {
    public:
        string rearrangeString(string str, int k) {
            if(k<=1)return str;
            vector<pair<int,int>> Counts(26,{0,-k});   //first: counts, second : index of last char in str;
            string res="";
            for(char ch : str)Counts[ch-'a'].first++;
            int len=str.size(),lenres=0,idx,maxCount;
            while(lenres<len){
                idx=-1,maxCount=0;
                for(int i=0;i<26;i++)
                        if(Counts[i].second+k<=lenres&&Counts[i].first>maxCount){
                                maxCount=Counts[i].first;
                                idx=i;
                        }
                if(idx>=0){
                    res+=char('a'+idx);
                    Counts[idx].first--;
                    Counts[idx].second=lenres++;
                }else return "";
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.