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

Solution 1: Greedy + Hash Table + Priority Queue (Max Heap)

We use a hash table or array \(\textit{cnt}\) to count the occurrences of each character in the string. Then, we use a max heap \(\textit{pq}\) to store each character and its count. Each element in the heap is a tuple \((v, c)\), where \(v\) is the count and \(c\) is the character.

When rearranging the string, we repeatedly pop the top element \((v, c)\) from the heap, add character \(c\) to the result string, and push \((v-1, c)\) into a queue \(\textit{q}\). When the length of the queue \(\textit{q}\) reaches \(k\) or more, we pop the front element; if its \(v\) is greater than \(0\), we push it back into the heap. Repeat this process until the heap is empty.

Finally, we check whether the length of the result string equals the original string. If so, we return the result string; otherwise, we return an empty string.

The time complexity is \(O(n \log n)\), where \(n\) is the length of the string. The space complexity is \(O(|\Sigma|)\), where \(|\Sigma|\) is the size of the character set, which is \(26\) in this problem.

Related problems:

• 767. Reorganize String

Python3JavaC++GoTypeScript

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        cnt = Counter(s)
        pq = [(-v, c) for c, v in cnt.items()]
        heapify(pq)
        q = deque()
        ans = []
        while pq:
            v, c = heappop(pq)
            ans.append(c)
            q.append((v + 1, c))
            if len(q) >= k:
                e = q.popleft()
                if e[0]:
                    heappush(pq, e)
        return "" if len(ans) < len(s) else "".join(ans)

class Solution {
    public String rearrangeString(String s, int k) {
        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 < cnt.length; ++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();
            p[0] -= 1;
            ans.append((char) ('a' + p[1]));
            q.offerLast(p);
            if (q.size() >= k) {
                p = q.pollFirst();
                if (p[0] > 0) {
                    pq.offer(p);
                }
            }
        }
        return ans.length() < s.length() ? "" : ans.toString();
    }
}

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

        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] > 0) {
                pq.emplace(cnt[i], i);
            }
        }

        queue<pair<int, int>> q;
        string ans;
        while (!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            p.first -= 1;
            ans.push_back('a' + p.second);
            q.push(p);
            if (q.size() >= k) {
                p = q.front();
                q.pop();
                if (p.first > 0) {
                    pq.push(p);
                }
            }
        }

        return ans.size() < s.size() ? "" : ans;
    }
};

func rearrangeString(s string, k int) string {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    pq := priorityqueue.NewWith(func(a, b any) int {
        x := a.([2]int)
        y := b.([2]int)
        return y[0] - x[0]
    })

    for i := 0; i < 26; i++ {
        if cnt[i] > 0 {
            pq.Enqueue([2]int{cnt[i], i})
        }
    }

    var q [][2]int
    var ans strings.Builder

    for pq.Size() > 0 {
        p, _ := pq.Dequeue()
        pair := p.([2]int)
        pair[0]--
        ans.WriteByte(byte('a' + pair[1]))
        q = append(q, pair)

        if len(q) >= k {
            front := q[0]
            q = q[1:]
            if front[0] > 0 {
                pq.Enqueue(front)
            }
        }
    }

    if ans.Len() < len(s) {
        return ""
    }
    return ans.String()
}

export function rearrangeString(s: string, k: number): string {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    const pq = new PriorityQueue<[number, number]>((a, b) => b[0] - a[0]);
    for (let i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            pq.enqueue([cnt[i], i]);
        }
    }

    const q: [number, number][] = [];
    const ans: string[] = [];
    while (!pq.isEmpty()) {
        const [count, idx] = pq.dequeue()!;
        const newCount = count - 1;
        ans.push(String.fromCharCode('a'.charCodeAt(0) + idx));
        q.push([newCount, idx]);
        if (q.length >= k) {
            const [frontCount, frontIdx] = q.shift()!;
            if (frontCount > 0) {
                pq.enqueue([frontCount, frontIdx]);
            }
        }
    }
    return ans.length < s.length ? '' : ans.join('');
}

Comments