Remove All Adjacent Duplicates In String

Cancel at the boundary

Use an array as a stack. For each character, if it equals the stack top, pop that top; otherwise push the character. The stack invariant is that it equals the fully reduced form of the processed prefix, so a new adjacent duplicate can only arise at its right boundary. Each character is pushed and popped at most once, giving O(n) time and O(n) space. Test an empty string, a pair that vanishes, chain reactions such as abbaca, all identical characters, and an odd count. Do not repeatedly delete substrings: each deletion can shift characters and turn this into O(n²) work. If the variant removes groups of size k, store character counts with the stack entries instead of only characters.