trivial solution c++, 9ms


  • 0
        string rearrangeString(string str, int k) {
            if(str.empty())
                return "";
            if(k<=1)
                return str;
            priority_queue<pair<int,char>> heap;
            vector<int> dict(256,0);
            for(char ch:str)
                dict[ch]++;
            for(int i=0;i<256;i++){
                if(dict[i]!=0){
                    heap.push({dict[i],char(i)});
                }
            }
            //prune
            if(heap.top().first==1)
                return str;
            int tileNumber=(str.size()-1)/(k);
            //prune
            if(heap.top().first>tileNumber+1)
                return "";
            string res(str.size(),'-');
            char ch=heap.top().second;
            int count=heap.top().first;
            heap.pop();
            for(int i=0;i<k;i++){
                for(int j=0;j<=tileNumber;j++){
                    if(i+j*k<str.size()){
                        res[i+j*k]=ch;
                        if(i+j*k+1<str.size()&&res[i+j*k+1]==ch||i+j*k-1>=0&&res[i+j*k-1]==ch)
                            return "";
                        count--;
                        if(count==0){
                            ch=heap.top().second;
                            count=heap.top().first;
                            heap.pop();
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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