We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove All Adjacent Duplicates In String

Difficulty: Easy

Problem Description

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Key Insights

  • The problem requires removing adjacent duplicate characters from a string.
  • A stack can be employed to efficiently handle the duplicates.
  • When iterating through the string, if the current character matches the character at the top of the stack, both are removed (i.e., popped from the stack).
  • If not, the current character is pushed onto the stack.
  • The final result can be constructed by joining the characters remaining in the stack.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we traverse the string once. Space Complexity: O(n), in the worst case, where all characters are unique and stored in the stack.

Solution

To solve the problem, we can utilize a stack data structure. The algorithm works by iterating through each character in the string. For each character:

  1. If the stack is not empty and the top of the stack is the same as the current character, pop the stack (remove the duplicate).
  2. Otherwise, push the current character onto the stack. Once we finish iterating through the string, the stack will contain the characters of the final string without any adjacent duplicates. We can then join the characters in the stack to form the result.

Code Solutions

def removeDuplicates(s: str) -> str:
    stack = []
    for char in s:
        # If stack is not empty and top element is same as current character
        if stack and stack[-1] == char:
            stack.pop()  # Remove the duplicate
        else:
            stack.append(char)  # Add current character to stack
    return ''.join(stack)  # Join remaining characters to form final string
← Back to All Questions