O(log(26)*N) solution, can be applied to other characters


  • 0
    S

    The time complexity of two auxiliary array method is actually (O(26*n)). This solution is (O(log(26)*n). However, due to the overhead of creating new data structure and hashing collision, the real time cost is actually higher than the two auxiliary array method....

    public class Solution {
        public String rearrangeString(String str, int k) {
            //greedy: we want to first arrange the character which has maximum number of remaining chars
            Map<Character, Integer> mapCount = new HashMap<>();
            //O(n)
            for (int i = 0; i < str.length(); i++) {
                mapCount.put(str.charAt(i), mapCount.getOrDefault(str.charAt(i),0) + 1);
            }
            
            //priority queue, ranking by the remaining counts.
            //O(log(26))
            PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((obj1, obj2) -> {
                if (obj2.getValue() != obj1.getValue()) return obj2.getValue() - obj1.getValue();
                else return obj1.getKey() - obj2.getKey();});
            pq.addAll(mapCount.entrySet());
            
            //tmpQueuue, when the character still can not be put back to the string because of lacking of distance, put
            //it in this temperory queue
            Queue<Map.Entry<Character,Integer>> tmpQ = new LinkedList<>();
            
            //run the algorithm
            StringBuilder sb = new StringBuilder();
            //O(log(26) * n)
            while (!pq.isEmpty()) {
                //get the character with largest remaining counts
                Map.Entry<Character,Integer> entry = pq.poll();
                //add it to the string
                entry.setValue(entry.getValue() - 1);
                sb.append(entry.getKey());
                //after the operation, add it to the tmp queue
                tmpQ.offer(entry);
                
                //if the character has at least k distance, put it back to the pq
                if (tmpQ.size() < k) continue;
                Map.Entry<Character, Integer> top = tmpQ.poll();
                //put the character back to the pq only if it still has remaing counts.
                if (top.getValue() > 0) pq.offer(top);
            }
    
            return sb.length() == str.length() ? sb.toString() : "";
        }
    }
    

Log in to reply
 

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