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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove All Adjacent Duplicates In String

Number: 1128

Difficulty: Easy

Paid? No

Companies: Meta, Grammarly, Amazon, Microsoft, Google, Bloomberg, Adobe, Zoho, Apple, Paytm

Problem Description

Given a string s consisting of lowercase English letters, repeatedly remove pairs of adjacent duplicate characters until no such pairs remain. The final string after all removals is guaranteed to be unique.

Key Insights

  • Utilize a stack to efficiently process and remove adjacent duplicates.
  • Iterate through each character in the string, comparing it with the top of the stack.
  • If the current character matches the top of the stack, pop the stack (i.e., remove the duplicate pair).
  • If there is no match, push the current character onto the stack.
  • Finally, join the characters remaining in the stack to obtain the result.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because each character is processed at most once. Space Complexity: O(n), in the worst-case scenario where no duplicates are found and all characters are stored in the stack.

Solution

The solution uses a stack-based approach. As we iterate through the input string, each character is compared with the top element of the stack. If they are the same, it means we have found an adjacent duplicate, so we remove the top element. Otherwise, we push the current character onto the stack. This method ensures that duplicate adjacent pairs are removed in a single pass through the string. Finally, the remaining characters in the stack are combined to form the final string, which is then returned as the unique answer.

Code Solutions

# Function to remove all adjacent duplicates in string
def remove_duplicates(s: str) -> str:
    # Initialize an empty list to use as a stack
    stack = []
    # Iterate through each character in the input string
    for char in s:
        # If stack is not empty and the top element equals the current character, pop the top element
        if stack and stack[-1] == char:
            stack.pop()
        else:
            # Otherwise, push the current character onto the stack
            stack.append(char)
    # Join the stack elements to form the final string result and return it
    return ''.join(stack)

# Example usage:
# result = remove_duplicates("abbaca")
# print(result)  # Output: "ca"
← Back to All Questions