Как реализовать сжатие строки с условием, что итоговая строка не длиннее входной

Что проверяют

Умеете ли вы за четверть часа написать аккуратный линейный алгоритм и заметить подводные камни Go: строки из байтов, дорогую конкатенацию, многозначные счётчики. Следующий вопрос обычно такой: а если во входной строке есть цифры или кириллица?

Как отвечать

Сначала уточните формат. Классика: RLE, где aaabccdddd превращается в a3b1c2d4, а если результат не короче исходной строки, возвращается исходная. Дальше каркас решения:

• один проход: считаем длину текущей серии, при смене символа дописываем символ и счётчик. Не забыть последнюю серию после цикла и пустую строку на входе;
• сборка результата: strings.Builder с Grow(len(s)) и strconv.Itoa или strconv.AppendInt для счётчика. Счётчик бывает двузначным, поэтому '0' + byte(count) не годится;
• ранний выход: как только длина билдера превысила len(s), дальше считать бессмысленно, возвращаем исходную строку;
• сложность: O(n) по времени и O(n) по памяти на результат.

Хорошо показать вариант, где счётчик 1 не пишется: aab даёт a2b. Тогда серия длиной k занимает не больше k символов, и результат гарантированно не длиннее входа без отдельной проверки. Минус формата: цифры во входе делают декодирование неоднозначным.

Про кодировку: len(s) в Go считает байты, и индексация строки тоже возвращает байт. Побайтовое RLE разрезает многобайтные символы, и в промежуточном результате получается невалидный UTF-8. Если вход может быть не ASCII, идите по строке через for _, r := range s, работайте с рунами, а длину сравнивайте в тех единицах, о которых говорит условие: байты или символы (utf8.RuneCountInString).

Где спотыкаются

Собирают результат через compressed += ... и fmt.Sprint. Каждая конкатенация копирует строку целиком, и на длинном входе линейный алгоритм превращается в квадратичный.

Молча работают с байтами. Строка аааааа на кириллице занимает 12 байт без единой пары одинаковых байтов подряд, и функция возвращает её несжатой, хотя шесть одинаковых букв это идеальная серия для RLE.

Не уточняют условие. «Не длиннее» и «короче» дают разный результат на строках вроде aabb, а цифры во входе делают сжатую строку нераскодируемой.