Katkat
Back

Remove All Adjacent Duplicate Pairs

WhatnotSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement an algorithm to repeatedly eliminate adjacent identical character pairs from a string until no adjacent duplicates remain, handling Unicode inputs in linear time.

Problem Statement

You are given a string s that may contain ASCII characters, symbols, and Unicode characters.

A duplicate pair consists of two equal adjacent characters. You must repeatedly remove duplicate adjacent pairs until the string is stable and no two adjacent characters are identical.

Note that pairwise reductions are evaluated from left to right: for example, in the string "aaa", the first two characters form a pair and are removed, leaving "a".

Write a function that returns the final string after all possible adjacent duplicate pairs have been removed. Your solution should operate in O(n) time.

Function Signature

def remove_adjacent_pairs(s: str) -> str:
    pass

Input & Output Format

  • Input: A string s.
  • Output: A string representing s after all adjacent duplicate pairs have been iteratively removed.

Examples

Example 1

Input: s = "abbaca"
Output: "ca"
Explanation:
- In "abbaca", the pair "bb" is removed to yield "aaca".
- In "aaca", the pair "aa" is removed to yield "ca".
- No more adjacent duplicate pairs exist.

Example 2

Input: s = "azxxzy"
Output: "ay"
Explanation:
- "xx" is removed, leaving "azz y" -> "azzy".
- "zz" is removed, leaving "ay".

Example 3

Input: s = "🔥✨✨🔥🚀"
Output: "🚀"
Explanation:
- "✨✨" is removed, which brings "🔥" next to "🔥".
- "🔥🔥" is removed, leaving "🚀".

Constraints

  • 0 <= len(s) <= 10^6
  • s consists of printable ASCII and Unicode code points.
  • Time Complexity: Must be O(n) where n is the length of s.
  • Space Complexity: O(n) auxiliary space.

Hints

Hint 1

Notice that when an adjacent pair is deleted, characters that were previously separated become newly adjacent to each other.

Hint 2

A stack data structure allows you to inspect the most recently added character and remove it in O(1) time if it matches the current character.

Hint 3

In Python, iterating directly over the string processes Unicode code points, but ensure your implementation joins the resulting stack into a string in a single O(n) step.

Follow-up questions

  • How would you generalize your solution to remove k consecutive identical characters rather than pairs?
  • How would you modify the solution to support user-perceived characters (grapheme clusters), such as emojis modified with zero-width joiners (ZWJ) or skin-tone modifiers?
  • If the input string is a continuous unbounded stream, how would you architect the pipeline to output simplified characters while minimizing buffer retention?