Remove adjacent duplicate characters

Problem:

Given a string s of lowercase English letters, repeatedly remove adjacent duplicate letters until no more can be removed.

Return the final string after all duplicate removals.

Example: 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.

Example: Input: s = "foobar"

Output: "fbar"

Explanation: We remove "oo" to get "fbar".

Solutions:

The simplest approach to removing adjacent duplicates is to use a stack. A stack helps efficiently track the last visited character while processing the string.

How It Works:

Iterate through the string:

• For each character, check the top of the stack (last added character).

Remove adjacent duplicates:

• If the current character matches the top of the stack, pop the top element (remove it) and do not add the current character.
• If they do not match, push the current character onto the stack.

Final String Construction:

• After processing all characters, the remaining elements in the stack form the final string without adjacent duplicates.

Example Walkthrough:

Input: "abbaca"

Processing:

• Stack: [a] (add 'a')
• Stack: [a, b] (add 'b')
• Stack: [a] (duplicate 'b' removed)
• Stack: [a, a] (add 'a')
• Stack: [] (duplicate 'a' removed)
• Stack: [c] (add 'c')
• Stack: [c, a] (add 'a')

Output: "ca"

Why Use a Stack?

• Efficient: Runs in O(n) time, as each character is pushed or popped once.
• Simple: Eliminates the need for complex string operations or recursion.:

public class RemoveAllDups {

    public String removeDuplicates(String s) {

        Stack<Character> stack = new Stack<Character>();
        for (Character c : s.toCharArray()) {
            if (stack.isEmpty() || stack.peek() != c){
                stack.push(c);
            } else {
                stack.pop();
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        RemoveAllDups removeAllDups = new RemoveAllDups();
        String input = "fooobar";
        System.out.println("Input : " + input + " Response: "  + removeAllDups.removeDuplicates(input));
        input = "abccba";
        System.out.println("Input : " + input + " Response: "  + removeAllDups.removeDuplicates(input));
    }
}

Comments are welcome.