Сегодня разберем классическую задачу, которая часто попадается на собеседованиях, так как проверяет больше не умение кодить, а умение выбирать корректный тип данных и не использовать избыточные структуры.

Задача: Сжатие строки (String Compression)

Условие:
Дана строка: aaabbccccdd
Необходимо сжать её, заменив последовательность одинаковых символов на: символ + количество повторений
Результат: a3b2c4d2
Если символ встречается один раз: abcd
Результат: abcd (не a1b1c1d1)

Решение:
Первый вопрос, который нужно задать - что выводить, если строка пустая или строка состоит из цифр? - по условию допускаем, что будут только буквы.
Далее идем по условию задачи:
Когда мы понимаем, что серия одинаковых символов закончилась?
Ответ простой — когда встретим другой символ

И вот тут многие совершают ошибку - используют HashMap. Но задача вообще не про подсчёт символов. Нам важно не количество каждого символа, а границы последовательностей. Поэтому достаточно одного прохода и двух переменных.

Алгоритм
- Проходим строку слева направо.

- Пока следующий символ совпадает с текущим — увеличиваем счётчик.

- Как только символ изменился:
записываем предыдущий символ;
если счётчик больше 1 — записываем его количество;
начинаем считать новую серию.

После цикла не забываем обработать последнюю группу символов.

public class StringCompression {

public static String compress(String s) {

if (s == null || s.isEmpty()) {
return s;
}

StringBuilder result = new StringBuilder();

int count = 1;

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
result.append(s.charAt(i - 1));

if (count > 1) {
result.append(count);
}

count = 1;
}
}

result.append(s.charAt(s.length() - 1));

if (count > 1) {
result.append(count);
}

return result.toString();
}

public static void main(String[] args) {
System.out.println(compress("aaabbccccdd"));
System.out.println(compress("abcd"));
}
}

Время: O(n)
Память: O(n)
(результирующая строка)