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 * 105
  • 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:

  1. Counting Characters:
    • Using Counter(s).items(), it counts the occurrences of each character in the string s.
    • 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.
  2. Heapify:
    • heapify(h) converts the list h into a heap, prioritizing characters by their negative counts, effectively making it a max heap based on character frequency.
  3. Initialization:
    • A queue q (implemented with deque) is used to keep track of characters and their remaining counts as they are used, ensuring they can only be re-added to the heap after k iterations.
    • An answer list ans is initialized to build the rearranged string.
  4. Rearrangement Process:
    • While the heap h is not empty, it repeatedly pops the character with the highest frequency (heappop(h)), appends it to ans, and decreases its count. This character is then added to the queue q.
    • If the length of q exceeds k, it means that a character at the front of the queue can now be safely re-added to the heap without violating the k distance constraint, as it has been at least k characters since it was last used. The character and its updated count are only re-added to the heap if the count is not zero (w != 0).
  5. Completion Check:
    • After processing all characters, it checks if the length of the answer list ans is equal to the length of the input string s. If not, this indicates that it was impossible to rearrange s according to the constraints, and an empty string is returned. Otherwise, it joins and returns the characters in ans as the rearranged string.
  • 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 'v-1==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 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)


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

All Problems

All Solutions