PrepBro
← Назад к вопросам

Сжатие строки

2.3 Middle🔥 131 комментариев
#Теория тестирования

Условие

Напишите функцию, которая сжимает строку с использованием подсчета повторяющихся символов. Если сжатая строка не короче оригинала, верните оригинал.

Пример

Вход: aabcccccaaa Выход: a2b1c5a3

Вход: abc Выход: abc

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Анализ задачи

Нужно сжать строку, заменяя группы одинаковых символов на символ + количество.

Решение 1: Простой алгоритм

def compressString(s):
    if not s:
        return s
    
    compressed = []
    count = 1
    
    for i in range(len(s)):
        if i + 1 >= len(s) or s[i] != s[i + 1]:
            compressed.append(s[i] + str(count))
            count = 1
        else:
            count += 1
    
    result = ''.join(compressed)
    return result if len(result) < len(s) else s

Решение 2: С itertools

from itertools import groupby

def compressString(s):
    compressed = ''.join(
        char + str(len(list(group)))
        for char, group in groupby(s)
    )
    return compressed if len(compressed) < len(s) else s

Решение 3: Java

public class StringCompression {
    public static String compressString(String s) {
        if (s == null || s.isEmpty()) return s;
        
        StringBuilder compressed = new StringBuilder();
        int count = 1;
        
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 >= s.length() || s.charAt(i) != s.charAt(i + 1)) {
                compressed.append(s.charAt(i)).append(count);
                count = 1;
            } else {
                count++;
            }
        }
        
        return compressed.length() < s.length() ? 
            compressed.toString() : s;
    }
}

Тестовые случаи

assert compressString("aabcccccaaa") == "a2b1c5a3"
assert compressString("abc") == "abc"
assert compressString("aaaa") == "a4"
assert compressString("a") == "a"
assert compressString("") == ""

Сложность

  • Время: O(n)
  • Память: O(n)

Ключевые моменты

  1. Сравниваем текущий символ со следующим
  2. Считаем последовательности одинаковых символов
  3. Возвращаем оригинал если сжатие не помогло

На собеседовании

  • Обсудите однопроходный алгоритм
  • Объясните сложность O(n)
  • Упомяните оптимизацию с предварительной проверкой
  • Обсудите граничные случаи