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

😎 Решение:

class Solution {
    public String rearrangeString(String s, int k) {
        Map<Character, Integer> freqs = new HashMap<>();
        int maxFreq = 0;
        
        for (char c : s.toCharArray()) {
            freqs.put(c, freqs.getOrDefault(c, 0) + 1);
            maxFreq = Math.max(maxFreq, freqs.get(c));
        }

        Set<Character> mostChars = new HashSet<>();
        Set<Character> secondChars = new HashSet<>();
        
        for (char c : freqs.keySet()) {
            if (freqs.get(c) == maxFreq) mostChars.add(c);
            else if (freqs.get(c) == maxFreq - 1) secondChars.add(c);
        }

        StringBuilder[] segments = new StringBuilder[maxFreq];
        for (int i = 0; i < maxFreq; i++) segments[i] = new StringBuilder();

        for (char c : mostChars) {
            for (int i = 0; i < maxFreq; i++) segments[i].append(c);
        }
        for (char c : secondChars) {
            for (int i = 0; i < maxFreq - 1; i++) segments[i].append(c);
        }

        int segmentId = 0;
        for (char c : freqs.keySet()) {
            if (mostChars.contains(c) || secondChars.contains(c)) continue;
            for (int freq = freqs.get(c); freq > 0; freq--) {
                segments[segmentId].append(c);
                segmentId = (segmentId + 1) % (maxFreq - 1);
            }
        }

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

        return String.join("", segments);
    }
}

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