Remove All Adjacent Duplicates In String

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. For example:

• Input: s = "abbaca" Output: "ca" Explanation: In "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
• Input: s = "azxxzy" Output: "ay"

Write a function to implement this.

def remove_duplicates(s: str) -> str:
    """Removes adjacent duplicate characters from a string.

    Args:
        s: The input string.

    Returns:
        The string after removing all adjacent duplicates.
    """
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

# Example usage:
s = "abbaca"
result = remove_duplicates(s)
print(f"Input: {s}, Output: {result}")  # Output: ca

s = "azxxzy"
result = remove_duplicates(s)
print(f"Input: {s}, Output: {result}")  # Output: ay

Explanation:

This Python code implements a solution to remove adjacent duplicate characters from a string using a stack. The algorithm iterates through the input string s. For each character, it checks if the stack is not empty and if 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 we pop the top element from the stack. Otherwise, we push the current character onto the stack. Finally, we join the remaining characters in the stack to form the final string.

Naive Solution

A naive solution would involve repeatedly iterating through the string and removing adjacent duplicates until no more duplicates can be found. This approach has a time complexity of O(n^2) in the worst case, where n is the length of the string.

def remove_duplicates_naive(s: str) -> str:
    """Removes adjacent duplicate characters from a string (naive solution)."""
    while True:
        modified = False
        new_s = ""
        i = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] == s[i + 1]:
                i += 2
                modified = True
            else:
                new_s += s[i]
                i += 1
        s = new_s
        if not modified:
            break
    return s

Optimal Solution

The optimal solution uses a stack to keep track of the characters. This approach has a time complexity of O(n), where n is the length of the string.

def remove_duplicates(s: str) -> str:
    """Removes adjacent duplicate characters from a string (optimal solution)."""
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

Big(O) Run-time Analysis:

The optimal solution iterates through the string once, and each character is either pushed onto the stack or popped from the stack at most once. Therefore, the time complexity is O(n), where n is the length of the string.

Big(O) Space Usage Analysis:

The space complexity is O(n) in the worst case, where n is the length of the string. This occurs when no duplicates are found, and all characters are pushed onto the stack.

Edge Cases:

1. Empty string: If the input string is empty, the function should return an empty string.
2. String with no duplicates: If the input string contains no adjacent duplicates, the function should return the original string.
3. String with all duplicates: If the input string consists of repeating pairs of characters (e.g., "aabbcc"), the function should return an empty string.
4. Long string: The function should handle long strings efficiently without exceeding memory limits.
5. String with mixed duplicates and unique characters: The function should correctly handle cases like "abccba" where some characters are duplicates and some are unique.