767. Reorganize String

using System;
using System.Collections.Generic;
public class Solution {
    public string ReorganizeString(string s) {
        int[] charCounts = new int[26];
        foreach (char c in s) {
            charCounts[c - 'a']++;
        }
        var pq = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.Enqueue(new int[] { charCounts[i], i + 'a' }, charCounts[i]);
            }
        }
        var result = new List<char>();
        while (pq.Count > 0) {
            var first = pq.Dequeue();
            if (result.Count == 0 || first[1] != result[^1]) {
                result.Add((char)first[1]);
                if (--first[0] > 0) {
                    pq.Enqueue(first, first[0]);
                }
            } else {
                if (pq.Count == 0) {
                    return "";
                }
                var second = pq.Dequeue();
                result.Add((char)second[1]);
                if (--second[0] > 0) {
                    pq.Enqueue(second, second[0]);
                }
                pq.Enqueue(first, first[0]);
            }
        }
        return new string(result.ToArray());
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string ReorganizeString(string s) {
        vector<int>& charCounts = new int[26];
        foreach (char c in s) {
            charCounts[c - 'a']++;
        }
        var pq = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.Enqueue(new int[] { charCounts[i], i + 'a' }, charCounts[i]);
            }
        }
        var result = new List<char>();
        while (pq.size() > 0) {
            var first = pq.Dequeue();
            if (result.size() == 0 || first[1] != result[^1]) {
                result.push_back((char)first[1]);
                if (--first[0] > 0) {
                    pq.Enqueue(first, first[0]);
                }
            } else {
                if (pq.size() == 0) {
                    return "";
                }
                var second = pq.Dequeue();
                result.push_back((char)second[1]);
                if (--second[0] > 0) {
                    pq.Enqueue(second, second[0]);
                }
                pq.Enqueue(first, first[0]);
            }
        }
        return new string(result.ToArray());
    }
}

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] charCounts = new int[26];
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.add(new int[]{charCounts[i], i + 'a'});
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (result.length() == 0 || first[1] != result.charAt(result.length() - 1)) {
                result.append((char)first[1]);
                if (--first[0] > 0) {
                    pq.add(first);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                int[] second = pq.poll();
                result.append((char)second[1]);
                if (--second[0] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }

        return result.toString();
    }
}

class Solution {
    reorganizeString(s) {
        const charCounts = new Array(26).fill(0);
        for (const c of s) {
            charCounts[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }

        const pq = new MaxPriorityQueue({ priority: x => x[0] });
        for (let i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.enqueue([charCounts[i], String.fromCharCode(i + 'a'.charCodeAt(0))]);
            }
        }

        let result = "";
        while (!pq.isEmpty()) {
            const first = pq.dequeue().element;
            if (result.length === 0 || first[1] !== result[result.length - 1]) {
                result += first[1];
                if (first[0] > 1) {
                    pq.enqueue([first[0] - 1, first[1]]);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                const second = pq.dequeue().element;
                result += second[1];
                if (second[0] > 1) {
                    pq.enqueue([second[0] - 1, second[1]]);
                }
                pq.enqueue(first);
            }
        }

        return result;
    }
}

import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        charCounts = [0] * 26
        for c in s:
            charCounts[ord(c) - ord('a')] += 1
        
        pq = []
        for i in range(26):
            if charCounts[i] > 0:
                heapq.heappush(pq, (-charCounts[i], chr(i + ord('a'))))
        
        result = []
        while pq:
            first = heapq.heappop(pq)
            if not result or first[1] != result[-1]:
                result.append(first[1])
                if -first[0] > 1:
                    heapq.heappush(pq, (first[0] + 1, first[1]))
            else:
                if not pq:
                    return ""
                second = heapq.heappop(pq)
                result.append(second[1])
                if -second[0] > 1:
                    heapq.heappush(pq, (second[0] + 1, second[1]))
                heapq.heappush(pq, first)
        
        return "".join(result)

import (
    "container/heap"
)

type Element struct {
    count int
    char  byte
}

type PriorityQueue []*Element

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].count > pq[j].count }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Element)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func reorganizeString(s string) string {
    charCounts := make([]int, 26)
    for _, c := range s {
        charCounts[c-'a']++
    }

    pq := &PriorityQueue{}
    heap.Init(pq)
    for i := 0; i < 26; i++ {
        if charCounts[i] > 0 {
            heap.Push(pq, &Element{charCounts[i], byte(i + 'a')})
        }
    }

    result := []byte{}
    for pq.Len() > 0 {
        first := heap.Pop(pq).(*Element)
        if len(result) == 0 || first.char != result[len(result)-1] {
            result = append(result, first.char)
            if first.count > 1 {
                first.count--
                heap.Push(pq, first)
            }
        } else {
            if pq.Len() == 0 {
                return ""
            }
            second := heap.Pop(pq).(*Element)
            result = append(result, second.char)
            if second.count > 1 {
                second.count--
                heap.Push(pq, second)
            }
            heap.Push(pq, first)
        }
    }

    return string(result)
}

Explanation

Algorithm

Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎