Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
counts = []
sa = list(s)
j = 0
for i in range(len(sa)):
sa[j] = sa[i]
if j == 0 or sa[j] != sa[j - 1]:
counts.append(1)
else:
incremented = counts.pop() + 1
if incremented == k:
j -= k
else:
counts.append(incremented)
j += 1
return "".join(sa[:j])
Ставь 👍 и забирай 📚 Базу знаний