Сложность: 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 {
fun removeDuplicates(s: String, k: Int): String {
val counts = mutableListOf<Int>()
val sa = s.toCharArray()
var j = 0
for (i in sa.indices) {
sa[j] = sa[i]
if (j == 0 || sa[j] != sa[j - 1]) {
counts.add(1)
} else {
val incremented = counts.removeAt(counts.size - 1) + 1
if (incremented == k) {
j -= k
} else {
counts.add(incremented)
}
}
j++
}
return String(sa, 0, j)
}
}Ставь 👍 и забирай 📚 Базу знаний