Задача: 358. Rearrange String k Distance Apart
Сложность: hard

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

class Solution {
    function rearrangeString($s, $k) {
        $freqs = [];
        $maxFreq = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!isset($freqs[$char])) {
                $freqs[$char] = 0;
            }
            $freqs[$char]++;
            $maxFreq = max($maxFreq, $freqs[$char]);
        }

        $mostChars = [];
        $secondChars = [];

        foreach ($freqs as $char => $freq) {
            if ($freq == $maxFreq) {
                $mostChars[] = $char;
            } else if ($freq == $maxFreq - 1) {
                $secondChars[] = $char;
            }
        }

        $segments = array_fill(0, $maxFreq, "");

        for ($i = 0; $i < $maxFreq; $i++) {
            foreach ($mostChars as $char) {
                $segments[$i] .= $char;
            }
            if ($i < $maxFreq - 1) {
                foreach ($secondChars as $char) {
                    $segments[$i] .= $char;
                }
            }
        }

        $segmentId = 0;

        foreach ($freqs as $char => $freq) {
            if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
                continue;
            }

            for ($j = 0; $j < $freq; $j++) {
                $segments[$segmentId] .= $char;
                $segmentId = ($segmentId + 1) % ($maxFreq - 1);
            }
        }

        for ($i = 0; $i < $maxFreq - 1; $i++) {
            if (strlen($segments[$i]) < $k) {
                return "";
            }
        }

        return implode("", $segments);
    }
}

Ставь 👍 и забирай 📚 Базу знаний