Katkat
Back

Repeatedly Delete Runs of k Adjacent Equal Characters from a String

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

Function Signature

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

Input: s = "abbbaac", k = 3
Output: "c"

Removing "bbb" leaves "aaac", which creates the run "aaa". Removing it leaves "c".

Example 2

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

Input: s = "aabbaa", k = 2
Output: ""

Removing "aa" and then "bb" leaves "aa", which is removed as well.