1047. Remove All Adjacent Duplicates In String Easy

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".

Approach

Input: A string s containing only lowercase English letters

Output: Repeatedly remove adjacent duplicated characters, and return the shortest possible string

This problem is a typical Pair Elimination Stack problem.

We use a stack stack to simulate the character processing process:

1. Iterate through each character in the string;
2. Before pushing into the stack, check if the current character is identical to the top character of the stack:
   • If they are the same, pop the top of the stack and skip the current character (i.e., "eliminate a pair");
   • Otherwise, push the current character onto the stack;
3. After traversal, the remaining characters in the stack are those that cannot be further eliminated. Join the stack together to form the new string and return it.

Implementation

python

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []  # Use a stack to save processed characters

        # Iterate through each character in the string
        for c in s:
            # If the stack is not empty, and the top character is the same as the current character,
            # it means they are an adjacent duplicate
            if stack and stack[-1] == c:
                stack.pop()  # Remove the top character to achieve pair elimination
            else:
                stack.append(c)  # Otherwise, push the current character
        
        # Finally, the remaining characters in the stack form the result 
        # after removing all adjacent duplicates
        return ''.join(stack)

javascript

/**
 * @param {string} s
 * @return {string}
 */
const removeDuplicates = function(s) {
    const stack = [];

    for (let c of s) {
        if (stack.length) {
            const top = stack.at(-1);

            if (c == top) {
                stack.pop();
                continue;
            }
        }

        stack.push(c);
    }

    return stack.join('');
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

1047. Remove All Adjacent Duplicates In String (English)

1047. 删除字符串中的所有相邻重复项 (Chinese)