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 * 10⁵
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 }

358 - Rearrange String k Distance Apart

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions