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

Средняя

medium , string , two pointers

29 April 2024

Описание задачи #

Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив по следующему принципу:

Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['a', 'n'], где a - исходный символ, n - количество повторений этого символа, идущих подряд. В случае если n — многозначное число, каждая цифра должна быть добавлена отдельным символом.
Если буква не повторяется - оставить ее без изменений.

Все изменения нужно совершить in-place, в качестве ответа функции вернуть количество символов в сжатой строке.

Ограничения #

Длина входящего массива от 1 до 2000 символов
Элементы массива - символы латиницы, цифры или знаки

Примеры #

Входные данные
```
chars = ["a","a","b","b","c","c","c"]
```
Ответ: 6

Исходный массив должен быть преобразован в ["a","2","b","2","c","3"]
Входные данные
```
chars = ["a"]
```
Ответ: 1
Входные данные
```
chars = chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
```
Ответ: 4

Исходный массив должен быть преобразован в ["a","b","1","2"]

Решение #

Задача решается достаточно элементарно, главная загвоздка - замена элементов in-place.

Для решения нам потребуется несколько индексов:

Индекс текущего элемента lastElemIdx
Индекс начала последовательности одинаковых элементов firstElemIdx
Индекс элемента, который будет заменен при сжатии строки newPositionIdx. Для эффективности решения мы будем заменять элементы исходного массива, а после «отрежем» хвост. В противном случае нам бы пришлось вырезать повторяющиеся символы, смещая хвост массива на n элементов влево, что значительно замедлит алгоритм.

Мы будем итерироваться по исходному массиву:

Пока текущий символ равен предыдущему, мы двигаемся вперед, запоминая последний индекс повторяющегося символа
В случае если текущий элемент не равен предыдущему (или же мы дошли до конца исходного массива):
1. Заносим элемент, который мы запомнили в исходный массив на позицию newPositionIdx
2. Инкрементируем newPositionIdx
3. При необходимости разницу между lastElemIdx и firstElemIdx превращаем в строку и посимвольно добавляем в следующие ячейки массива (и инкрементируем newPositionIdx для каждого вставленного символа)
4. Запоминаем новый символ, как начало следующей последовательности, и переносим позицию firstElemIdx

В конце нам останется «отрезать» хвост у исходного массива.

package main

import "strconv"

func compress(chars []byte) int {
	newPositionIdx := 0

	for firstElemIdx := 0; firstElemIdx < len(chars); firstElemIdx++ {
		lastChar := chars[firstElemIdx]

		lastElemIdx := firstElemIdx + 1
		for lastElemIdx < len(chars) && chars[lastElemIdx] == lastChar {
			lastElemIdx++
		}

		chars[newPositionIdx] = chars[lastElemIdx-1]
		newPositionIdx++

		if counter := lastElemIdx - firstElemIdx; counter > 1 {
			for _, countChar := range strconv.Itoa(counter) {
				chars[newPositionIdx] = byte(countChar)
				newPositionIdx++
			}

		}

		firstElemIdx = lastElemIdx - 1
	}

	chars = chars[:newPositionIdx]
	return len(chars)
}

export const compress = (chars: string[]): number => {
	let newPositionIdx = 0;

	for (let firstElemIdx = 0; firstElemIdx < chars.length; firstElemIdx++) {
		const lastChar = chars[firstElemIdx];

		let lastElemIdx = firstElemIdx + 1;
		while (lastElemIdx < chars.length && chars[lastElemIdx] === lastChar) {
			lastElemIdx++;
		}

		chars[newPositionIdx] = chars[lastElemIdx - 1];
		newPositionIdx++;

		const counter = lastElemIdx - firstElemIdx;
		if (counter > 1) {
			for (const countChar of counter.toString()) {
				chars[newPositionIdx] = countChar;
				newPositionIdx++;
			}
		}

		firstElemIdx = lastElemIdx - 1;
	}

	chars.splice(newPositionIdx, chars.length - newPositionIdx);
	return chars.length;
}

Оценка сложности #

n - количество элементов в массиве.

По времени

Сложность по времени O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность по памяти O(1), так как мы модифицируем массив in-place.

Оригинал задачи на Leetcode

Algorithmics