Recursively remove all adjacent duplicates

Problem Statement

Given a string, recursively remove all adjacent duplicate characters until no adjacent duplicates remain.

Example:

• Input: "geeksforgeeg"
• Output: "gksfor"
• Explanation:
  • "geeksforgeeg" → remove "ee" → "gksforgeeg"
  • "gksforgeeg" → remove "ee" → "gksforgeg"
  • "gksforgeg" → remove "gg" → "gksforge"
  • "gksforge" → no adjacent duplicates → "gksfor" (after removing "ge")

Actually: "geeksforgeeg" → "gksforgg" → "gksfor"

Approach 1: Brute Force (Repeated Scanning)

Intuition

Keep scanning the string and removing adjacent duplicates until no more duplicates are found in a complete pass.

Algorithm

1. Scan string for adjacent duplicates
2. If found, remove them and restart from beginning
3. If no duplicates found in complete pass, return result

public class Solution {
    public String removeAdjacentDuplicates(String s) {
        boolean found = true;
        
        while (found) {
            found = false;
            StringBuilder result = new StringBuilder();
            int i = 0;
            
            while (i < s.length()) {
                if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
                    found = true;
                    char c = s.charAt(i);
                    while (i < s.length() && s.charAt(i) == c) {
                        i++;
                    }
                } else {
                    result.append(s.charAt(i));
                    i++;
                }
            }
            
            s = result.toString();
        }
        
        return s;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Each pass is O(n), may need O(n) passes
• Space Complexity: O(n) - For storing intermediate results

Approach 2: Using Stack (Optimal)

Intuition

Use a stack to track characters. When we encounter a character, if it matches the top of stack, pop it (removing the pair). Otherwise, push the new character.

Algorithm

1. Initialize empty stack
2. For each character:
   • If stack is not empty and top matches current, pop
   • Otherwise, push current character
3. Build result from stack

Wait, the above only handles pairs. For removing ALL adjacent duplicates (including groups of 3+), we need:

Better Stack Approach (Handles Recursion)

Actually, let me provide a cleaner recursive solution:

public class Solution {
    public String removeAdjacentDuplicates(String s) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        boolean removed = false;
        
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            
            if (j - i == 1) {
                result.append(s.charAt(i));
            } else {
                removed = true;
            }
            
            i = j;
        }
        
        if (removed) {
            return removeAdjacentDuplicates(result.toString());
        }
        
        return result.toString();
    }
}

Optimal Stack Solution

Actually for proper recursive removal (where "aab" becomes "" after "aa" is removed and then checking again), here's the correct approach:

Complexity Analysis

• Time Complexity: O(n) with proper stack approach
• Space Complexity: O(n) for stack/result

Key Takeaways

1. Stack is the key data structure for this problem
2. The problem has two variants:
   • Remove pairs only (easier)
   • Remove all adjacent duplicates recursively (harder)
3. For recursive removal, after removing a group, new adjacents may form
4. String as stack (string.push_back(), string.pop_back()) is efficient in C++
5. Related: Remove All Adjacent Duplicates in String II (with k duplicates)