Practice/Meta/Leetcode 1047. Remove All Adjacent Duplicates In String

Leetcode 1047. Remove All Adjacent Duplicates In String

CodingMust

Problem

You are given a string consisting of lowercase English letters. Your task is to repeatedly remove pairs of adjacent identical characters until no more such pairs exist. Each removal may create new adjacent pairs that also need to be removed. Return the final string after all possible removals have been completed.

For example, if the string is "abbaca", you would first remove "bb" to get "aaca", then remove "aa" to get "ca", which is the final result.

Requirements

1. Process the string to remove all adjacent duplicate character pairs
2. Continue removing until no adjacent duplicates remain
3. Return the resulting string (which may be empty)
4. Handle strings containing only lowercase letters

Constraints

• 1 ≤ length of string ≤ 100,000
• String contains only lowercase English letters (a-z)
• Your solution should run in O(n) time where n is the length of the string
• Space complexity should be O(n) or better

Examples

Example 1:

` Input: s = "abbaca" Output: "ca" Explanation:

• Remove "bb" → "aaca"
• Remove "aa" → "ca"
• No more adjacent duplicates `

Example 2:

` Input: s = "azxxzy" Output: "ay" Explanation:

• Remove "xx" → "azzy"
• Remove "zz" → "ay" `

Example 3:

Input: s = "aabbcc" Output: "" Explanation: All characters form adjacent pairs and collapse completely