[LeetCode][Kotlin] 1209. Remove All Adjacent Duplicates in String II

1209. Remove All Adjacent Duplicates in String II

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

 

We repeatedly make k duplicate removals on s until we no longer can.

 

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

문자열 s와 정수 k가 주어지면, k 중복 제거는 s에서 k개의 인접하고 동일한 문자를 선택하여 제거하고, 삭제된 부분 문자열의 왼쪽과 오른쪽을 서로 연결하는 것으로 구성됩니다. 

더 이상 할 수 없을 때까지 s에서 k번 중복 제거를 반복합니다. 

이러한 모든 중복 제거가 이루어진 후 최종 문자열을 반환합니다. 답이 고유하다는 것이 보장됩니다.

 

Example 1:

Input: s = "abcd", k = 2

Output: "abcd"

Explanation: There's nothing to delete.

 

Example 2:

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"

 

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2

Output: "ps"

 

Constraints:

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s only contains lowercase English letters.

---

코드

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val stack = ArrayDeque<Pair<Char, Int>>()

        s.forEach { c ->
            if (stack.isNotEmpty() && stack.last().first == c) {
                val (char, count) = stack.removeLast()
                stack.add(char to count + 1)
            } else {
                stack.add(c to 1)
            }

            if (stack.last().second == k) {
                stack.removeLast()
            }
        }

        var res = ""
        for ((char, count) in stack) {
            res += char.toString().repeat(count)
        }

        return res
    }
}