Welcome to Subscribe On Youtube
358. Rearrange String k Distance Apart
Description
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 * 10^{5}
s
consists of only lowercase English letters.0 <= k <= s.length
Solutions
The method uses a max heap to ensure that the character with the highest remaining frequency is selected next, while a queue maintains the constraint of k
distance to avoid repeating characters.
Steps and Explanation:
 Counting Characters:
 Using
Counter(s).items()
, it counts the occurrences of each character in the strings
.  It creates a heap
h
from these counts, with each element being a tuple of the negative count (to create a max heap, since Python’s heapq module provides a min heap by default) and the character itself.
 Using
 Heapify:
heapify(h)
converts the listh
into a heap, prioritizing characters by their negative counts, effectively making it a max heap based on character frequency.
 Initialization:
 A queue
q
(implemented withdeque
) is used to keep track of characters and their remaining counts as they are used, ensuring they can only be readded to the heap afterk
iterations.  An answer list
ans
is initialized to build the rearranged string.
 A queue
 Rearrangement Process:
 While the heap
h
is not empty, it repeatedly pops the character with the highest frequency (heappop(h)
), appends it toans
, and decreases its count. This character is then added to the queueq
.  If the length of
q
exceedsk
, it means that a character at the front of the queue can now be safely readded to the heap without violating thek
distance constraint, as it has been at leastk
characters since it was last used. The character and its updated count are only readded to the heap if the count is not zero (w != 0
).
 While the heap
 Completion Check:
 After processing all characters, it checks if the length of the answer list
ans
is equal to the length of the input strings
. If not, this indicates that it was impossible to rearranges
according to the constraints, and an empty string is returned. Otherwise, it joins and returns the characters inans
as the rearranged string.
 After processing all characters, it checks if the length of the answer list

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 s, int k) { unordered_map<char, int> cnt; for (char c : s) ++cnt[c]; priority_queue<pair<int, char>> pq; for (auto& [c, v] : cnt) pq.push({v, c}); queue<pair<int, char>> q; string ans; while (!pq.empty()) { auto [v, c] = pq.top(); pq.pop(); ans += c; q.push({v  1, c}); if (q.size() >= k) { auto p = q.front(); q.pop(); if (p.first) { pq.push(p); } } } return ans.size() == s.size() ? ans : ""; } };

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)) # enqueue even if 'v1==0' # not '>=' # use example k=1, then q size is 2, then q can pop one out if len(q) > k: # @note: this is avoid you pick up same char in the same ksegment. 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 actualpositivecount > 1 tmp.append((count+1, ch)) s = s[1:] for count, ch in tmp: heapq.heappush(pq, (count, ch)) return "".join(sb)

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 any) { *h = append(*h, v.(pair)) } func (h *hp) Pop() any { a := *h; v := a[len(a)1]; *h = a[:len(a)1]; return v }