Katkat
Back

Remove Adjacent Duplicate Runs of Length K

AttentiveSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement a linear-time string reduction algorithm that repeatedly eliminates adjacent runs of k identical characters using a stack.

Problem Statement

You are given a string s consisting of lowercase English letters and an integer k.

A k-duplicate removal consists of choosing k adjacent and equal letters from s and removing them. Removing a run of k letters causes the adjacent substrings on both sides to concatenate, which may create new runs of k identical letters.

Repeatedly make k-duplicate removals until no group of k consecutive identical characters remains. Return the final resulting string. The answer is guaranteed to be unique.

Function Signature

def remove_duplicates(s: str, k: int) -> str:
    pass

Examples

Example 1

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
1. Delete "eee" -> "ddbbcccbdaa"
2. Delete "ccc" -> "ddbbbdaa"
3. Delete "bbb" -> "dddaa"
4. Delete "ddd" -> "aa"

Example 2

Input: s = "pbbcggttciiippooaass", k = 2
Output: "ps"
Explanation:
"bb", "gg", "tt", "pp", "oo", and "aa" can be removed. Cascading deletions will eventually leave "ps".

Constraints

  • 1 len(s) or no identical runs reach length k).
  • A long run contains a multiple of k characters (e.g., 2 * k duplicates should all be removed across consecutive passes).

Hints

Hint 1

A brute-force approach scanning and rebuilding the string repeatedly can degrade to O(n^2 / k) time.

Hint 2

Use a stack that stores pairs of (character, count) representing the contiguous sequence up to the current index.

Hint 3

When the count of the character at the top of the stack hits k, pop it immediately so the surrounding characters merge.

Follow-up questions

  • How would you modify your solution if the rule changed to remove runs of length at least k (greedy removal of the entire contiguous run)?
  • Can you achieve O(1) auxiliary space if the input is provided as a mutable array of characters (in-place two-pointer approach)?
  • How would you handle an infinite stream of characters where you must maintain the current reduced string length at every step?