Remove adjacent duplicates in String

XXX. Remove Adjacent Duplicates in String

String

Stack

Problem Statement:

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

• Two characters are adjacent and equal should be removed
• Process should continue until no more removals can be done
• Final string should contain no adjacent duplicates

Algorithm:

1. **Stack Approach**:
   • Use stack to track characters
   • Pop when duplicate found
   • Build final string from stack

Implementation:

Java Solution:

public String removeDuplicates(String S) {
    Stack stack = new Stack<>();
    
    // Process each character
    for (char c : S.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c)   // Found duplicate
            stack.pop();
        else                                         // New character
            stack.push(c);
    }
    
    // Build result string
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty())
        sb.append(stack.pop());
    
    return sb.reverse().toString();                  // Reverse to get correct order
}
                

Python Solution:

def removeDuplicates(self, S: str) -> str:
    stack = []
    
    # Process each character
    for c in S:
        if stack and stack[-1] == c:    # Found duplicate
            stack.pop()
        else:                           # New character
            stack.append(c)
    
    return ''.join(stack)               # Join characters to form string
                

C++ Solution:

string removeDuplicates(string S) {
    string stack;                       // Use string as stack
    
    // Process each character
    for (char c : S) {
        if (!stack.empty() && stack.back() == c)  // Found duplicate
            stack.pop_back();
        else                                      // New character
            stack.push_back(c);
    }
    
    return stack;                       // String already in correct order
}
                

Complexity:

Time Complexity: O(n), where n is string length
Space Complexity: O(n) for stack storage

Explanation:

• **Stack Logic**:
  • Stack maintains non-duplicate characters
  • Compare current with stack top