Katkat
Back

Remove runs of length at least k

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates string manipulation, run-length detection, and algorithmic efficiency, focusing on tracking and removing maximal contiguous character groups. It is commonly asked in the Coding & Algorithms domain to assess practical application–level skills in designing linear-time, linear-space implementations that handle dynamic sequence collapses using appropriate data structures.

Given a string s and an integer k (k >= 2), repeatedly remove every maximal contiguous group of the same character whose length is at least k, deleting the entire group (not just a chunk of size k). After each deletion, the remaining parts of the string collapse together and the process continues until no more deletions are possible. Return the final string. Examples:

  • s = 'abbbbc', k = 3 -> remove 'bbbb' -> 'ac'.
  • s = 'aaabbbcc', k = 3 -> remove 'aaa' and 'bbb' -> 'cc'.
  • s = 'baaabbbaac', k = 3 -> remove 'aaa' and 'bbb' -> 'bc' (no further deletions). Design an algorithm that runs in O(n) time and O(n) space using a stack-based approach (character + run length), and explain how you detect new removable runs formed after collapses.