Domain 1EasyCORE

Remove All Adjacent Duplicates In String

The problem requires us to remove all adjacent duplicate characters from a given string `S` until no more duplicates can be removed. The input is a string of lowercase English letters, and the output should be the final string after all possible adjacent duplicate removals have been made. It's guaranteed that there will be a unique solution.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack

1047. Remove All Adjacent Duplicates In String

Model: qwen2.5-coder:14b
Topics: Stack
FAANG asked: 1
Acceptance rate: 71.2%


Problem Breakdown

The problem requires us to remove all adjacent duplicate characters from a given string S until no more duplicates can be removed. The input is a string of lowercase English letters, and the output should be the final string after all possible adjacent duplicate removals have been made. It’s guaranteed that there will be a unique solution.

Inputs:

  • A string S consisting of lowercase English letters.

Outputs:

  • A string with all adjacent duplicates removed.

Implicit Constraints or Edge Cases:

  • The input string can be empty.
  • The input string might not contain any duplicates, in which case the output will be the same as the input.
  • The input string could have all characters the same, leading to an empty string as the output after removing all adjacent duplicates.

Intuition

A brute-force approach would involve repeatedly scanning the string and removing adjacent duplicates until no more can be found. This approach is inefficient because it may require multiple passes over the string, resulting in a time complexity of O(n^2) in the worst case.

The key insight to improve this is to use a stack data structure. By iterating through the string once, we can efficiently manage and remove adjacent duplicates by leveraging the LIFO (Last In, First Out) property of stacks. This approach ensures that each character is processed only once, leading to an optimal time complexity of O(n).

Approach

  1. Initialize a Stack: Use a stack to keep track of characters as we iterate through the string.
  2. Iterate Through the String:
    • For each character in the string, check if the stack is not empty and the top element of the stack is equal to the current character.
    • If they are equal, it means we have found an adjacent duplicate, so pop the top element from the stack (remove the last added character).
    • If they are not equal, push the current character onto the stack.
  3. Construct the Result: After processing all characters, the stack will contain the final string with all adjacent duplicates removed. Convert the stack to a string and return it.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. Each character is processed at most twice (once when pushed onto the stack and once when popped).
  • Space Complexity: O(n) in the worst case, where all characters are unique and remain in the stack.

Solution

def removeDuplicates(S: str) -> str:
    stack = []
    
    for char in S:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    
    return ''.join(stack)

Edge Cases Handled

  • Empty String: If the input string is empty, the stack remains empty, and the function returns an empty string.
  • No Duplicates: If there are no adjacent duplicates in the string, all characters will be pushed onto the stack, and the final result will be the same as the input string.
  • All Characters Same: If all characters in the string are the same, they will all be removed one by one, resulting in an empty string.