Задача: 358. Rearrange String k Distance Apart
Дана строка 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)
👉Новости 👉Платформа