Remove All Adjacent Duplicates in String II
Medium · Stack & Strings · String · Stack
Problem
You are given a string s and an integer k. A removal picks k adjacent, equal letters and deletes them, joining the text on either side.
Keep applying removals until none is possible, and return the final string. The result does not depend on the order of the removals.
Examples
Input: s = "abbbaac", k = 3 Output: "c"
Deleting bbb leaves aaac, and then deleting aaa leaves c.
Input: s = "abcd", k = 2 Output: "abcd"
No letter repeats, so nothing can be removed.
Input: s = "abcddcba", k = 2 Output: ""
dd goes first, then the c run, then b, then a: nothing is left.
Constraints
- 1 <= len(s) <= 10^5
- 2 <= k <= 10^4
- s contains lowercase letters
Approaches
- Baseline: remove the first run, rescan — time O(n² / k), space O(n)
Follow-up
If k were 2, a plain stack of letters would do. Why do counts become necessary when k is larger?
Related problems
Start free on Cariara · Coding problems · System design studio
