Katkat
Back

Repeatedly Delete Adjacent Duplicate Pairs or Whole Runs of Equal Characters

WhatnotSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

A string coding problem with two modes: repeatedly delete pairs of equal adjacent characters, or, as the follow-up, delete whole runs of equal adjacent characters, always the leftmost run first, and return what remains. It tests simulating cascading deletions efficiently and handling runs that merge after a deletion.

You are given a string s of lowercase letters and a flag remove_whole_runs. Delete adjacent duplicates repeatedly until none remain, and return the final string.

The interview first asked for the base rule, which deletes equal adjacent characters two at a time. The follow-up dropped the fixed group size: whenever equal characters are adjacent, all of them are deleted, however many there are. Here one function covers both rules, selected by the flag.

Function Signature

def remove_adjacent_duplicates(s: str, remove_whole_runs: bool) -> str:

Rules

  • A run is a maximal block of consecutive equal characters. For example, "abbbac" has the runs a, bbb, a, c.
  • When remove_whole_runs is False: repeatedly choose two adjacent equal characters and delete both. Stop when no two adjacent characters are equal. The final string is the same whichever pair is chosen at each step.
  • When remove_whole_runs is True: repeatedly delete the entire leftmost run of length two or more. Stop when every run has length one. Here the order of deletions can change the result, so the leftmost rule is part of the specification.
  • After a deletion, the characters on either side of the deleted block become adjacent and may form a new run. Characters that are never deleted keep their original order.
  • Return the final string, which may be empty.

Constraints

  • 1 <= len(s) <= 10^5
  • s consists only of lowercase English letters a to z.
  • remove_whole_runs is True or False.

Examples

Example 1

Input: s = "abbaca", remove_whole_runs = False
Output: "ca"

Deleting bb gives "aaca", and deleting aa gives "ca".

Example 2

Input: s = "abbbac", remove_whole_runs = True
Output: "c"

The run bbb is deleted, giving "aac"; then the run aa is deleted, giving "c". With remove_whole_runs = False, the same string gives "abac": one pair of b characters is deleted and a single b remains.

Example 3

Input: s = "abbaa", remove_whole_runs = True
Output: ""

The leftmost run bb goes first, leaving "aaa", which is then deleted. Deleting the final aa first would have left "abb" and then "a", which the leftmost rule does not allow.