Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/358.html

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".

 

Example 1:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

Example 2:

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

Example 3:

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of only lowercase English letters.
  • 0 <= k <= s.length

Algorithm

We need a hash table to establish the mapping between characters and their occurrences, and then a heap is needed to store each heap of mappings, sorted according to the number of occurrences.

Then if the heap is not empty, we start the loop. We find the smaller value between the length of k and str, and then traverse from 0 to this smaller value.

For each traversed value,

  • if the heap is empty at this time, indicating that this position cannot be filled with characters, return an empty string,
  • otherwise we take a pair of mappings from the top of the heap, and then add letters to the result, then the number of mappings is reduced by 1,
    • if the number after subtracting 1 If it is still greater than 0, we add this mapping to the temporary set v, and at the same time the number of str len is reduced by 1.

After traversing once, we add the mapping pairs in the temporary set to the heap.

Code

  • import java.util.*;
    
    public class Rearrange_String_k_Distance_Apart {
    
        public static void main(String[] args) {
            Rearrange_String_k_Distance_Apart out = new Rearrange_String_k_Distance_Apart();
            Solution s = out.new Solution();
    
            /*
                a,3
                c,2
                b,2
                a,2
                d,1
                c,1
                b,1
                a,1
             */
            System.out.println(s.rearrangeString("aaadbbcc", 2)); // output: acbadcba
    
    
            /*
                a,3
                c,1
                a,2
                b,1
                a,1
                acaba
             */
            System.out.println(s.rearrangeString("aaabc", 2));
    
    
    
            System.out.println(s.rearrangeString("aaabc", 3));
        }
    
        public class Solution {
            public String rearrangeString(String str, int k) {
    
                if (k == 0) {
                    return str;
                }
    
                // build up freq map
                int len = str.length();
                Map<Character, Integer> counts = new HashMap<>(); // char => its count
                for (int i = 0; i < len; i++) {
                    char ch = str.charAt(i);
                    int n = 1;
                    if (counts.containsKey(ch)) {
                        n = counts.get(ch) + 1;
                    }
                    counts.put(ch, n);
                }
    
                // high count char at top of heap
                // to ensure the order of the chars with same count, they should show up in same order.
                PriorityQueue<Pair> pq = new PriorityQueue<>(10, (p1, p2) -> {
                    if (p1.count != p2.count) return p2.count - p1.count;
                    else return p2.ch - p1.ch;
                });
    
                // build up heap
                for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
                    pq.offer(new Pair(entry.getKey(), entry.getValue())); // pick the most show-up char first.
                }
    
                StringBuilder sb = new StringBuilder();
                while (!pq.isEmpty()) {
                    List<Pair> tmp = new ArrayList<>(); // @note: this is avoid you pick up same char in the same k-segment.
                    int d = Math.min(k, len); // final segment, could be shorter one
                    for (int i = 0; i < d; i++) { // one segment
                        if (pq.isEmpty()) { // cannot form result
                            return "";
                        }
                        Pair p = pq.poll();
                        System.out.println(p.ch + "," + p.count);
                        sb.append(p.ch);
                        if (--p.count > 0) {
                            tmp.add(p);
                        }
                        len--;
                    }
    
                    /*
                        In addition, after each pop-up character with the most occurrences, it cannot be directly put into the heap.
                        
                        Because putting it directly into the heap may be popped out again next time, it should be put into a temporary array and reinserted into the heap after a single operation.
                     */
                    for (Pair p : tmp) {
                        pq.offer(p);
                    }
                }
    
                return sb.toString();
    
            }
    
            class Pair {
                char ch;
                int count;
    
                Pair(char c, int t) {
                    ch = c;
                    count = t;
                }
            }
        }
    }
    
    ############
    
    class Solution {
        public String rearrangeString(String s, int k) {
            int n = s.length();
            int[] cnt = new int[26];
            for (char c : s.toCharArray()) {
                ++cnt[c - 'a'];
            }
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > 0) {
                    pq.offer(new int[] {cnt[i], i});
                }
            }
            Deque<int[]> q = new ArrayDeque<>();
            StringBuilder ans = new StringBuilder();
            while (!pq.isEmpty()) {
                var p = pq.poll();
                int v = p[0], c = p[1];
                ans.append((char) ('a' + c));
                q.offer(new int[] {v - 1, c});
                if (q.size() >= k) {
                    p = q.pollFirst();
                    if (p[0] > 0) {
                        pq.offer(p);
                    }
                }
            }
            return ans.length() == n ? ans.toString() : "";
        }
    }
    
  • class Solution {
    public:
        string rearrangeString(string str, int k) {
            if (k == 0) return str;
            string res;
            int len = (int)str.size();
            unordered_map<char, int> m;
            priority_queue<pair<int, char>> q;
            for (auto a : str) ++m[a];
            for (auto it = m.begin(); it != m.end(); ++it) {
                q.push({it->second, it->first});
            }
            while (!q.empty()) {
                vector<pair<int, int>> v;
                int cnt = min(k, len);
                for (int i = 0; i < cnt; ++i) {
                    if (q.empty()) return "";
                    auto t = q.top(); q.pop();
                    res.push_back(t.second);
                    if (--t.first > 0) v.push_back(t);
                    --len;
                }
                for (auto a : v) q.push(a);
            }
            return res;
        }
    };
    
  • from heapq import heapify
    
    class Solution:
        def rearrangeString(self, s: str, k: int) -> str:
            h = [(-v, c) for c, v in Counter(s).items()]
            heapify(h)
            q = deque()
            ans = []
            while h:
                v, c = heappop(h)
                v *= -1
                ans.append(c)
                q.append((v - 1, c))
                if len(q) >= k: # @note: this is avoid you pick up same char in the same k-segment.
                    w, c = q.popleft()
                    if w: # w!=0
                        heappush(h, (-w, c))
            return "" if len(ans) != len(s) else "".join(ans)
    
    #############
    
    import collections
    import heapq
    
    class Solution:
        def rearrangeString(self, s: str, k: int) -> str:
            if k == 0:
                return s
            
            counts = collections.Counter(s)
            
            pq = []
            for ch, count in counts.items():
                heapq.heappush(pq, (-count, ch))
            
            sb = []
            while pq:
                tmp = []
                d = min(k, len(s))
                for i in range(d):
                    if not pq:
                        return ""
                    count, ch = heapq.heappop(pq)
                    sb.append(ch)
                    if count < -1: # pushed in as negated, so it's: if actual-positive-count > 1
                        tmp.append((count+1, ch))
                    s = s[1:]
                
                for count, ch in tmp:
                    heapq.heappush(pq, (count, ch))
            
            return "".join(sb)
    
    ############
    
    class Solution(object):
      def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if k < 2:
          return s
        d = collections.Counter(s)
        heap = [(-d[key], key) for key in d] # inversed to negative, so heap is a max heap
        heapq.heapify(heap)
        ans = []
        while len(ans) < len(s):
          temp = []
          for _ in range(k):
            if not heap:
              return ""
            freq, c = heapq.heappop(heap)
            freq += 1 # when enqueue, inversed to negative, so here +1 is decreasing its actual count
            ans.append(c)
            if len(ans) == len(s):
              return "".join(ans)
            if freq < 0:
              temp.append((freq, c))
          for freq, c in temp:
            heapq.heappush(heap, (freq, c))
        return "".join(ans)
    
    
  • func rearrangeString(s string, k int) string {
    	cnt := map[byte]int{}
    	for i := range s {
    		cnt[s[i]]++
    	}
    	pq := hp{}
    	for c, v := range cnt {
    		heap.Push(&pq, pair{v, c})
    	}
    	ans := []byte{}
    	q := []pair{}
    	for len(pq) > 0 {
    		p := heap.Pop(&pq).(pair)
    		v, c := p.v, p.c
    		ans = append(ans, c)
    		q = append(q, pair{v - 1, c})
    		if len(q) >= k {
    			p = q[0]
    			q = q[1:]
    			if p.v > 0 {
    				heap.Push(&pq, p)
    			}
    		}
    	}
    	if len(ans) == len(s) {
    		return string(ans)
    	}
    	return ""
    }
    
    type pair struct {
    	v int
    	c byte
    }
    
    type hp []pair
    
    func (h hp) Len() int { return len(h) }
    func (h hp) Less(i, j int) bool {
    	a, b := h[i], h[j]
    	return a.v > b.v
    }
    func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
    func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    

All Problems

All Solutions