Quick Overview

Given a lowercase string and an integer k, repeatedly delete k adjacent equal characters, letting the remaining parts join and possibly form new runs, until no deletion is possible, then return what remains. It tests efficient simulation of cascading removals on strings of up to 100,000 characters.

Repeatedly Delete Runs of k Adjacent Equal Characters from a String

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a string `s` of lowercase English letters and an integer `k`. A removal deletes `k` adjacent, equal characters from the string, and the parts to the left and right of them then join together. Keep making removals until none is possible, and return the final string. ### Function Signature ```python def remove_k_adjacent_duplicates(s: str, k: int) -> str: ``` ### Rules - A removal deletes exactly `k` characters. A run of more than `k` equal characters loses `k` of them per removal, so a run whose length is not a multiple of `k` leaves characters behind. - Joining the two sides after a removal can create a new run of equal characters, which can then be removed in turn. - The final string does not depend on the order in which removals are made, so the answer is unique. - Return the empty string if every character is removed. ### Constraints - `1 <= len(s) <= 10^5` - `2 <= k <= 10^4` - `s` contains only lowercase English letters `'a'` to `'z'`. ### Examples **Example 1** ```text Input: s = "abbbaac", k = 3 Output: "c" ``` Removing `"bbb"` leaves `"aaac"`, which creates the run `"aaa"`. Removing it leaves `"c"`. **Example 2** ```text Input: s = "xyyzzzyx", k = 2 Output: "xzyx" ``` Removing `"yy"` gives `"xzzzyx"`. The run `"zzz"` loses two characters and leaves one `z`, giving `"xzyx"`, which has no two adjacent equal characters. **Example 3** ```text Input: s = "aabbaa", k = 2 Output: "" ``` Removing `"aa"` and then `"bb"` leaves `"aa"`, which is removed as well.

Overview: Given a lowercase string and an integer k, repeatedly delete k adjacent equal characters, letting the remaining parts join and possibly form new runs, until no deletion is possible, then return what remains. It tests efficient simulation of cascading removals on strings of up to 100,000 characters.

You are given a string `s` of lowercase English letters and an integer `k`. A removal deletes `k` adjacent, equal characters from the string, and the parts to the left and right of them then join together. Keep making removals until none is possible, and return the final string. Implement `remove_k_adjacent_duplicates(s, k)`. ### Rules - A removal deletes exactly `k` characters. A run of more than `k` equal characters loses `k` of them per removal, so a run whose length is not a multiple of `k` leaves characters behind. - Joining the two sides after a removal can create a new run of equal characters, which can then be removed in turn. - The final string does not depend on the order in which removals are made, so the answer is unique. - Return the empty string if every character is removed. - `k` may be larger than the length of `s`; then no removal is possible and `s` is returned unchanged. ### Constraints - `1 <= len(s) <= 10^5` - `2 <= k <= 10^4` - `s` contains only lowercase English letters `'a'` to `'z'`. - No value exceeds 2^31 - 1, so a 32-bit `int` is enough in every language; the returned string has at most 10^5 characters. ### Example 1 ```text Input: s = "abbbaac", k = 3 Output: "c" ``` Removing `"bbb"` leaves `"aaac"`, which creates the run `"aaa"`. Removing it leaves `"c"`. ### Example 2 ```text Input: s = "xyyzzzyx", k = 2 Output: "xzyx" ``` Removing `"yy"` gives `"xzzzyx"`. The run `"zzz"` loses two characters and leaves one `z`, giving `"xzyx"`, which has no two adjacent equal characters.

Constraints

  • 1 <= len(s) <= 10^5
  • 2 <= k <= 10^4
  • s contains only lowercase English letters 'a' to 'z'.

Examples

Input: ('abbbaac', 3)

Expected Output: 'c'

Explanation: Source example 1: removing 'bbb' joins the a's into 'aaa', which is removed, leaving 'c'.

Input: ('xyyzzzyx', 2)

Expected Output: 'xzyx'

Explanation: Source example 2: 'yy' is removed and the run 'zzz' loses two characters, leaving one z.

Hints

  1. Because the final string does not depend on the order of removals, you are free to perform them in whatever order is most convenient.
  2. A run of L equal letters that never joins anything else leaves L mod k of them behind.
  3. After a removal, only the characters immediately on either side of the gap can form a new run, so the next removal can only happen where the previous one was.

Loading coding console...

Show the approach

Approach

Scan s from left to right while keeping a stack of runs, each a (letter, count) pair, that spells the fully reduced form of the prefix read so far. For each character: if it equals the letter of the top run, increment that run's count; otherwise push a new run with count 1. When the top count reaches k, those k equal characters are adjacent in the current string, so they form a valid removal: pop the run. The run underneath (if any) is now adjacent to whatever character comes next, which is exactly the join the rules describe, so cascades happen automatically when later characters extend it.

Invariant: after every step, adjacent runs on the stack have different letters and every count lies between 1 and k-1, so the string the stack spells contains no removable block. Every pop is a legal removal, and since the final string does not depend on the order of removals, reducing the prefix first and then handling the new character yields the unique answer. At the end, concatenate each run's letter repeated count times.

Edge cases: k larger than len(s) (no run can reach k, so s is returned unchanged); a run of length L that never joins anything leaves L mod k characters; the remainder of one run can join a later run of the same letter and reach k only after the join, or overshoot k and leave a new remainder; a joined run of exactly k-1 must stay; if everything is removed the stack is empty and the empty string is returned.

Time complexity:
O(n)
Space complexity:
O(n)