1047. Remove All Adjacent Duplicates In String

LeetCode Link: 1047. Remove All Adjacent Duplicates In String

Problem Definition

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.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation:
For example, 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".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Thought Process

This problem is closely related to 20. Valid Parentheses, where we also used a stack-like mechanism for matching and removing certain pairs.

Key Idea

To remove adjacent duplicates, you only need to know if the current character matches the most recent character you kept (which can be tracked in a stack or similar structure). Here’s how:

Iterate through the string character by character.
For each character:
- If the stack is not empty and the top of the stack matches this character, pop it from the stack (removing the duplicate).
- Otherwise, push this character onto the stack.
At the end, any characters left in the stack represent the final string without adjacent duplicates.

Solution

Method 1: Using a List as a Stack

class Solution:
    def removeDuplicates(self, s: str) -> str:
        """
        Approach:
        Use a list 'res' as a stack. For each character:
        - If the stack is not empty and the top equals the current char, pop.
        - Otherwise, push the current char onto the stack.
        """
        res = []  # stack
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)

This approach is straightforward, using Python’s built-in list as a stack (append and pop operations). The final joining step yields the resultant string.

Method 2: Simulating a Stack with Two Pointers

In some situations, you might not be allowed to use an explicit stack structure. You can simulate it using two pointers (slow and fast) on the same list.

Here below is the illustration:

This avoids explicit stack usage but mimics the same behavior.

class SolutionTwoPointers:
    def removeDuplicates(self, s: str) -> str:
        """
        Approach:
        Convert the string to a list and use two pointers (slow, fast).
        - Assign res[slow] = res[fast].
        - If res[slow] == res[slow - 1], slow -= 1 (remove duplicate).
        - Otherwise, slow += 1.
        - Always fast += 1.
        """
        res = list(s)
        slow, fast = 0, 0
        length = len(res)

        while fast < length:
            res[slow] = res[fast]
            # Check if we've created a duplicate with the newly placed character
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1

        # Join the valid portion of the list into a string
        return "".join(res[:slow])

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. Each character is processed once, either pushed or popped.
Space Complexity: O(n) in the worst case (if there are no adjacent duplicates, you might store all characters). The additional space for the stack/list is typically considered separate from the input.

Takeaways

Stack-Like Structure: Removing adjacent duplicates often suggests a stack-based approach.
Alternate Approaches: Even if a stack isn’t allowed, it can often be emulated via pointers.
Efficiency: The solution runs in O(n) time.