Question

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

358	Rearrange String k Distance Apart

Given a non-empty string str and an integer k,
rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters.
If it is not possible to rearrange the string, return an empty string "".

Example 1:

str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.

Example 2:

str = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string.

Example 3:

str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

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

Java

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 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;
    }
};

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)

358 - Rearrange String k Distance Apart

Question

Algorithm

Code

All Problems

All Solutions