Задача: 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 {
    func rearrangeString(_ s: String, _ k: Int) -> String {
        var freqs = [Character: Int]()
        var maxFreq = 0
        
        for char in s {
            freqs[char, default: 0] += 1
            maxFreq = max(maxFreq, freqs[char]!)
        }

        var mostChars = Set<Character>()
        var secondChars = Set<Character>()
        
        for (char, freq) in freqs {
            if freq == maxFreq {
                mostChars.insert(char)
            } else if freq == maxFreq - 1 {
                secondChars.insert(char)
            }
        }

        var segments = [String](repeating: "", count: maxFreq)

        for char in mostChars {
            for i in 0..<maxFreq {
                segments[i].append(char)
            }
        }
        for char in secondChars {
            for i in 0..<maxFreq-1 {
                segments[i].append(char)
            }
        }

        var segmentId = 0
        for (char, freq) in freqs {
            if mostChars.contains(char) || secondChars.contains(char) {
                continue
            }
            for _ in 0..<freq {
                segments[segmentId].append(char)
                segmentId = (segmentId + 1) % (maxFreq - 1)
            }
        }

        for i in 0..<maxFreq-1 {
            if segments[i].count < k {
                return ""
            }
        }

        return segments.joined()
    }
}

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