Simple C++ code only using two vectors, running in 39ms


  • 1
    S
    class Solution{
    public:
        string rearrangeString(string str, int k){
            vector<int> Idx(26,-k),Counts(26,0);
            string res="";
            for(char ch : str)Counts[ch-'a']++;
            int tmpcount,idx,len;
            while(true){
                tmpcount=0,idx=-1,len=res.size();
                for(int i=0;i<26;i++)
                    if(Counts[i]>tmpcount&&len-Idx[i]>=k){
                        tmpcount=Counts[i];
                        idx=i;
                    }
                if(idx<0)break;
                Counts[idx]--;
                Idx[idx]=len;
                res+=('a'+idx);
            }
            return res.size()<str.size()? "":res;
        }
    };

Log in to reply
 

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