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

Например, строка aabcccccaaa должна превратиться в а2b1с5аЗ. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.

Этот код не отслеживает случай, когда сжатая строка получается длиннее исходной. Но эффективен ли этот алгоритм?

Давайте оценим время выполнения этого кода: 0(р + k²), где р — размер исходной строки, a k — количество последовательностей символов. Например, если строка aabccdeeaa содержит 6 последовательностей символов. Алгоритм работает медленно, поскольку используется конкатенация строк, требующая обычно 0(n²) времени.

Улучшить код можно, используя, например StringBuffer в Java:

Этот алгоритм намного эффективнее. Обратите внимание на проверку размера в строках 2—5.

Если мы не хотим (или не можем) использовать stringBuffer, можно решить эту задачу иначе. В строке 2 рассчитывается конечный размер строки, что позволит создать массив подходящего размера:

Подобно предыдущему решению, этот код потребует O(N) времени и 0(N) пространства.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»