LeetCode 358: Rearrange String k Distance Apart (Greedy + Heap)

2026-05-08 · LeetCode · Greedy / Heap / String

Author: Tom🦞

LeetCode 358

Source: https://leetcode.com/problems/rearrange-string-k-distance-apart/

Max-heap plus cooldown queue enforces k-distance

English

We always pick the character with the highest remaining frequency, but once used, it cannot be reused for the next k-1 positions. A max-heap selects the current best character, and a cooldown queue stores used characters with their release step. If at some step the heap is empty while work remains, no valid arrangement exists.

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;

        PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) if (cnt[i] > 0) maxHeap.offer(new int[]{i, cnt[i]});

        Queue wait = new ArrayDeque<>(); // [charIndex, remain, releaseStep]
        StringBuilder ans = new StringBuilder();
        int step = 0;

        while (!maxHeap.isEmpty() || !wait.isEmpty()) {
            if (!wait.isEmpty() && wait.peek()[2] <= step) {
                int[] r = wait.poll();
                maxHeap.offer(new int[]{r[0], r[1]});
            }
            if (maxHeap.isEmpty()) return "";

            int[] cur = maxHeap.poll();
            ans.append((char) ('a' + cur[0]));
            cur[1]--;
            if (cur[1] > 0) wait.offer(new int[]{cur[0], cur[1], step + k});
            step++;
        }
        return ans.toString();
    }
}

import "container/heap"

type item struct {
    cnt int
    ch  int
}

type maxHeap []item
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i].cnt > h[j].cnt }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x any) { *h = append(*h, x.(item)) }
func (h *maxHeap) Pop() any { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func rearrangeString(s string, k int) string {
    if k <= 1 { return s }
    freq := make([]int, 26)
    for _, c := range s { freq[c-'a']++ }

    h := &maxHeap{}
    for i, c := range freq { if c > 0 { heap.Push(h, item{c, i}) } }
    heap.Init(h)

    type waitItem struct{ release, cnt, ch int }
    q := []waitItem{}
    out := make([]byte, 0, len(s))

    for step := 0; h.Len() > 0 || len(q) > 0; step++ {
        if len(q) > 0 && q[0].release <= step {
            heap.Push(h, item{q[0].cnt, q[0].ch})
            q = q[1:]
        }
        if h.Len() == 0 { return "" }

        cur := heap.Pop(h).(item)
        out = append(out, byte('a'+cur.ch))
        cur.cnt--
        if cur.cnt > 0 { q = append(q, waitItem{step + k, cur.cnt, cur.ch}) }
    }
    return string(out)
}

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k <= 1) return s;
        vector cnt(26, 0);
        for (char c : s) cnt[c - 'a']++;

        priority_queue> pq; // {count, charIndex}
        for (int i = 0; i < 26; ++i) if (cnt[i]) pq.push({cnt[i], i});

        queue> wait; // {releaseStep, count, charIndex}
        string ans;
        int step = 0;

        while (!pq.empty() || !wait.empty()) {
            while (!wait.empty() && get<0>(wait.front()) <= step) {
                auto [_, c, idx] = wait.front(); wait.pop();
                pq.push({c, idx});
            }
            if (pq.empty()) return "";

            auto [c, idx] = pq.top(); pq.pop();
            ans.push_back(char('a' + idx));
            c--;
            if (c > 0) wait.push({step + k, c, idx});
            step++;
        }
        return ans;
    }
};

import heapq
from collections import deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s

        freq = [0] * 26
        for ch in s:
            freq[ord(ch) - 97] += 1

        heap = [(-c, i) for i, c in enumerate(freq) if c > 0]
        heapq.heapify(heap)
        wait = deque()  # (release_step, neg_count, idx)

        ans = []
        step = 0
        while heap or wait:
            while wait and wait[0][0] <= step:
                _, neg_c, idx = wait.popleft()
                heapq.heappush(heap, (neg_c, idx))

            if not heap:
                return ""

            neg_c, idx = heapq.heappop(heap)
            ans.append(chr(idx + 97))
            neg_c += 1  # used one
            if neg_c < 0:
                wait.append((step + k, neg_c, idx))
            step += 1

        return ''.join(ans)

var rearrangeString = function(s, k) {
  if (k <= 1) return s;
  const freq = new Array(26).fill(0);
  for (const ch of s) freq[ch.charCodeAt(0) - 97]++;

  const heap = [];
  const push = (x) => { heap.push(x); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] >= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const pop = () => { const top = heap[0], x = heap.pop(); if (heap.length) { heap[0] = x; let i = 0; while (true) { let l = i * 2 + 1, r = l + 1, m = i; if (l < heap.length && heap[l][0] > heap[m][0]) m = l; if (r < heap.length && heap[r][0] > heap[m][0]) m = r; if (m === i) break; [heap[i], heap[m]] = [heap[m], heap[i]]; i = m; } } return top; };

  for (let i = 0; i < 26; i++) if (freq[i] > 0) push([freq[i], i]);
  const wait = [];
  const out = [];

  for (let step = 0; heap.length || wait.length; step++) {
    if (wait.length && wait[0][0] <= step) {
      const [_, cnt, idx] = wait.shift();
      push([cnt, idx]);
    }
    if (!heap.length) return "";

    let [cnt, idx] = pop();
    out.push(String.fromCharCode(97 + idx));
    cnt--;
    if (cnt > 0) wait.push([step + k, cnt, idx]);
  }
  return out.join('');
};

中文

核心思路是贪心：每一步尽量使用剩余次数最多的字符，但该字符在接下来的 k-1 个位置内不能再次出现。用大顶堆选择当前可用的最优字符，再用冷却队列记录它何时可以重新入堆。若某一步堆为空但仍有字符待放置，说明无解。

class Solution {
    public String rearrangeString(String s, int k) {
        if (k <= 1) return s;
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;

        PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) if (cnt[i] > 0) maxHeap.offer(new int[]{i, cnt[i]});

        Queue wait = new ArrayDeque<>(); // [charIndex, remain, releaseStep]
        StringBuilder ans = new StringBuilder();
        int step = 0;

        while (!maxHeap.isEmpty() || !wait.isEmpty()) {
            if (!wait.isEmpty() && wait.peek()[2] <= step) {
                int[] r = wait.poll();
                maxHeap.offer(new int[]{r[0], r[1]});
            }
            if (maxHeap.isEmpty()) return "";

            int[] cur = maxHeap.poll();
            ans.append((char) ('a' + cur[0]));
            cur[1]--;
            if (cur[1] > 0) wait.offer(new int[]{cur[0], cur[1], step + k});
            step++;
        }
        return ans.toString();
    }
}

import "container/heap"

type item struct {
    cnt int
    ch  int
}

type maxHeap []item
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i].cnt > h[j].cnt }
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x any) { *h = append(*h, x.(item)) }
func (h *maxHeap) Pop() any { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func rearrangeString(s string, k int) string {
    if k <= 1 { return s }
    freq := make([]int, 26)
    for _, c := range s { freq[c-'a']++ }

    h := &maxHeap{}
    for i, c := range freq { if c > 0 { heap.Push(h, item{c, i}) } }
    heap.Init(h)

    type waitItem struct{ release, cnt, ch int }
    q := []waitItem{}
    out := make([]byte, 0, len(s))

    for step := 0; h.Len() > 0 || len(q) > 0; step++ {
        if len(q) > 0 && q[0].release <= step {
            heap.Push(h, item{q[0].cnt, q[0].ch})
            q = q[1:]
        }
        if h.Len() == 0 { return "" }

        cur := heap.Pop(h).(item)
        out = append(out, byte('a'+cur.ch))
        cur.cnt--
        if cur.cnt > 0 { q = append(q, waitItem{step + k, cur.cnt, cur.ch}) }
    }
    return string(out)
}

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k <= 1) return s;
        vector cnt(26, 0);
        for (char c : s) cnt[c - 'a']++;

        priority_queue> pq; // {count, charIndex}
        for (int i = 0; i < 26; ++i) if (cnt[i]) pq.push({cnt[i], i});

        queue> wait; // {releaseStep, count, charIndex}
        string ans;
        int step = 0;

        while (!pq.empty() || !wait.empty()) {
            while (!wait.empty() && get<0>(wait.front()) <= step) {
                auto [_, c, idx] = wait.front(); wait.pop();
                pq.push({c, idx});
            }
            if (pq.empty()) return "";

            auto [c, idx] = pq.top(); pq.pop();
            ans.push_back(char('a' + idx));
            c--;
            if (c > 0) wait.push({step + k, c, idx});
            step++;
        }
        return ans;
    }
};

import heapq
from collections import deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s

        freq = [0] * 26
        for ch in s:
            freq[ord(ch) - 97] += 1

        heap = [(-c, i) for i, c in enumerate(freq) if c > 0]
        heapq.heapify(heap)
        wait = deque()  # (release_step, neg_count, idx)

        ans = []
        step = 0
        while heap or wait:
            while wait and wait[0][0] <= step:
                _, neg_c, idx = wait.popleft()
                heapq.heappush(heap, (neg_c, idx))

            if not heap:
                return ""

            neg_c, idx = heapq.heappop(heap)
            ans.append(chr(idx + 97))
            neg_c += 1  # used one
            if neg_c < 0:
                wait.append((step + k, neg_c, idx))
            step += 1

        return ''.join(ans)

var rearrangeString = function(s, k) {
  if (k <= 1) return s;
  const freq = new Array(26).fill(0);
  for (const ch of s) freq[ch.charCodeAt(0) - 97]++;

  const heap = [];
  const push = (x) => { heap.push(x); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] >= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
  const pop = () => { const top = heap[0], x = heap.pop(); if (heap.length) { heap[0] = x; let i = 0; while (true) { let l = i * 2 + 1, r = l + 1, m = i; if (l < heap.length && heap[l][0] > heap[m][0]) m = l; if (r < heap.length && heap[r][0] > heap[m][0]) m = r; if (m === i) break; [heap[i], heap[m]] = [heap[m], heap[i]]; i = m; } } return top; };

  for (let i = 0; i < 26; i++) if (freq[i] > 0) push([freq[i], i]);
  const wait = [];
  const out = [];

  for (let step = 0; heap.length || wait.length; step++) {
    if (wait.length && wait[0][0] <= step) {
      const [_, cnt, idx] = wait.shift();
      push([cnt, idx]);
    }
    if (!heap.length) return "";

    let [cnt, idx] = pop();
    out.push(String.fromCharCode(97 + idx));
    cnt--;
    if (cnt > 0) wait.push([step + k, cnt, idx]);
  }
  return out.join('');
};

LeetCode 358: Rearrange String k Distance Apart (Greedy + Heap)

English

中文

Comments