#ЛитКод
Задача: 767. Reorganize String

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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());
    }
}

👉Новости 👉База вопросов