Problem Statement

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.

Examples

1. • Input: s = "abccba"
   • Output: ""
   • Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
2. • Input: s = "foobar"
   • Output: "fbar"
   • Explanation: We remove "oo" to get "fbar".
3. • Input: s = "fooobar"
   • Output: "fobar"
   • Explanation: We remove the pair "oo" to get "fobar".
4. • Input: s = "abcd"
   • Output: "abcd"
   • Explanation: No adjacent duplicates so no changes.

Constraints:

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

Solution

This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.

Algorithm Walkthrough

1. Initialize an empty stack.
2. Loop through the characters in the given string s.
3. For each character:
   • If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
   • Otherwise, push the current character onto the stack.
4. Finally, build the result string from the characters remaining on the stack.

Code

Here is the code for this algorithm:

Time and Space Complexity

The time complexity of this algorithm is O(N), where N is the length of s, because we perform one operation per character in s. The space complexity is also O(N), as in the worst case, every character in s is pushed onto the stack.