Задача: 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⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

from collections import defaultdict

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        freqs = defaultdict(int)
        max_freq = 0
        
        for char in s:
            freqs[char] += 1
            max_freq = max(max_freq, freqs[char])
        
        most_chars = {char for char, freq in freqs.items() if freq == max_freq}
        second_chars = {char for char, freq in freqs.items() if freq == max_freq - 1}
        
        segments = [list() for _ in range(max_freq)]
        
        for i in range(max_freq):
            for char in most_chars:
                segments[i].append(char)
            if i < max_freq - 1:
                for char in second_chars:
                    segments[i].append(char)
        
        segment_id = 0
        
        for char, freq in freqs.items():
            if char in most_chars or char in second_chars:
                continue
            for _ in range(freq):
                segments[segment_id].append(char)
                segment_id = (segment_id + 1) % (max_freq - 1)
        
        for i in range(max_freq - 1):
            if len(segments[i]) < k:
                return ""
        
        return "".join("".join(segment) for segment in segments)

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