Katkat
Back

Repeatedly Remove Adjacent Equal Characters

OmnissaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle recursive reduction patterns in a string using a stack-based approach to achieve linear time complexity.

Problem Statement

You are given a string s consisting of lowercase English letters. A "removal" consists of choosing two adjacent and equal characters and deleting them. You must repeatedly make these removals until no two adjacent characters are equal. Return the final string after all such removals have been made.

It can be proven that the final result is unique regardless of the order of removals.

Function Signature

def remove_duplicates(s: str) -> str:

Constraints

  • `1 "aaca" (remove 'bb')
  1. "aaca" -> "ca" (remove 'aa')

Example 2: Input: s = "azxxzy" Output: "ay" Explanation:

  1. "azxxzy" -> "azzy" (remove 'xx')
  2. "azzy" -> "ay" (remove 'zz')

Edge Cases

  • String with no duplicates (e.g., "abcd") should return the original string.
  • String where all characters are removed (e.g., "abba") should return an empty string.
  • Single character strings (e.g., "z") should return the input.

Hints

Hint 1

Consider using a stack to keep track of the characters you have processed so far.

Hint 2

When iterating through the string, if the current character matches the top of the stack, it means you have found a pair to remove; pop the stack.

Hint 3

If the current character does not match the stack top (or the stack is empty), push the current character onto the stack.

Follow-up questions

  • What is the time and space complexity of your solution, and can you explain why?
  • How would you modify this algorithm if you needed to remove characters only when three consecutive characters are identical instead of two?
  • Could you implement this solution using a pointer-based approach on a mutable character array to save space instead of using an explicit stack?