Naive Solution

A brute force approach would involve iterating through the string and, for each pair of adjacent characters, checking if they are equal. If they are, remove them and repeat the process until no more adjacent duplicates exist. This method involves string manipulation at each removal, which can be inefficient.

def remove_duplicates_naive(s):
    while True:
        found_duplicate = False
        new_s = ""
        i = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] == s[i+1]:
                i += 2
                found_duplicate = True
            else:
                new_s += s[i]
                i += 1
        s = new_s
        if not found_duplicate:
            break
    return s

• Time Complexity: O(N^2) in the worst case, where N is the length of the string. This is because, in each iteration, we might iterate through the string, and in the worst case, we might need to iterate multiple times.
• Space Complexity: O(N), as we create a new string in each iteration.

Optimal Solution

A more efficient approach utilizes a stack. Iterate through the string, and for each character:

1. If the stack is empty or the current character is different from the top of the stack, push the character onto the stack.
2. If the current character is the same as the top of the stack, pop the stack.

Finally, the remaining characters in the stack form the final string.

def remove_duplicates_stack(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

• Time Complexity: O(N), where N is the length of the string. Each character is processed exactly once.
• Space Complexity: O(N) in the worst case, where the stack stores all the characters if there are no duplicates.

Edge Cases

• Empty string: Should return an empty string.
• String with no duplicates: Should return the original string.
• String with all duplicates: Should return an empty string.
• String with mixed duplicates and unique characters: Should correctly remove only the adjacent duplicates.

Example Usages

print(remove_duplicates_stack("abbaca"))  # Output: ca
print(remove_duplicates_stack("azxxzy"))  # Output: ay
print(remove_duplicates_stack(""))  # Output: ""
print(remove_duplicates_stack("abc"))  # Output: abc
print(remove_duplicates_stack("aa"))  # Output: ""