Сжатие подряд идущих символов по ключу

33. Сжать подряд идущие одинаковые символы по коэффициенту

Условие задачи:
Даны строка text и целое число k > 0.

Необходимо обработать каждую группу подряд идущих одинаковых символов: каждые k символов такой группы заменить одним символом.

Например:

при k = 1 строка не изменяется;
"aa" при k = 2 превращается в "a";
"aaa" при k = 3 превращается в "a";
"cccc" при k = 2 превращается в "cc";
если длина группы не делится на k, оставшиеся символы сохраняются.

Код:

class Main {
    public static void main(String[] args) {
        String text = "aabbababaacccdaaad";

        System.out.println(compress(text, 2));
        System.out.println(compress(text, 1));
        System.out.println(compress(text, 3));
    }

    public static String compress(String text, int k) {
        // TODO
    }
}

Примеры:

text = "aabbababaacccdaaad", k = 2
→ "abababaccdaad"

text = "aabbababaacccdaaad", k = 1
→ "aabbababaacccdaaad"

text = "aabbababaacccdaaad", k = 3
→ "aabbababaacdad"

Спойлеры к решению

Подсказки

💡 Достаточно один раз пройти по строке, считая длину текущей группы одинаковых символов.
💡 Когда символ меняется, нужно добавить в результат сжатую текущую группу.
💡 Для группы длины count количество символов после сжатия равно count / k + count % k.
💡 Не забудь отдельно обработать последнюю группу.

Решение

public static String compress(String text, int k) {
    Objects.requireNonNull(text, "text");

    if (k <= 0) {
        throw new IllegalArgumentException("k должен быть больше 0");
    }

    if (text.isEmpty() || k == 1) {
        return text;
    }

    StringBuilder result = new StringBuilder(text.length());

    char current = text.charAt(0);
    int count = 1;

    for (int i = 1; i < text.length(); i++) {
        char ch = text.charAt(i);

        if (ch == current) {
            count++;
        } else {
            appendCompressed(result, current, count, k);
            current = ch;
            count = 1;
        }
    }

    appendCompressed(result, current, count, k);

    return result.toString();
}

private static void appendCompressed(
        StringBuilder result,
        char ch,
        int count,
        int k
) {
    int newCount = count / k + count % k;

    for (int i = 0; i < newCount; i++) {
        result.append(ch);
    }
}

Для каждой последовательности одинаковых символов сначала определяется её длина.

Например, при:

count = 7
k = 3

получаем две полные группы по три символа и один оставшийся символ:

7 / 3 = 2
7 % 3 = 1

Следовательно, после сжатия останется:

2 + 1 = 3 символа

Это вычисляется выражением:

int newCount = count / k + count % k;

Для примера:

"cccc", k = 2

count = 4
4 / 2 + 4 % 2 = 2

→ "cc"

А для:

"aaaa", k = 3

count = 4
4 / 3 + 4 % 3 = 2

→ "aa"

Последнюю группу необходимо обработать после завершения цикла:

appendCompressed(result, current, count, k);

иначе она не попадёт в результат.

Временная сложность — O(n), где n — длина строки. Дополнительная память — O(n) для результирующей строки.