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)