Remove all adjacent duplicates in string

83.Remove All Adjacent Duplicates in String

Stack

String

Problem Statement:

Given a string S, remove all adjacent duplicates in the string. The result should not contain any adjacent duplicates, and the operation should continue until no further adjacent duplicates can be removed.

Algorithm:

1. Use a stack to iteratively remove adjacent duplicate characters:
• If the stack is not empty and the top character is the same as the current character, pop the stack to remove the duplicate.
• Otherwise, push the current character onto the stack.
2. Once all characters are processed, use a StringBuilder to reconstruct the string by popping elements from the stack in reverse order.

Complexity:

Time: O(n), where n is the length of the string | Space: O(n)

Java Implementation:

public String removeDuplicates(String S) {
    Stack stack = new Stack<>();
    
    // Traverse each character in the string
    for (char c : S.toCharArray()) {
        // Remove adjacent duplicates by popping the stack
        if (!stack.isEmpty() && stack.peek() == c) 
            stack.pop();
        else 
            stack.push(c); // Otherwise, push the character onto the stack
    }
    
    // Reconstruct the string from the stack
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty())
        sb.append(stack.pop());
    
    // Reverse the result since characters are added in reverse order
    return sb.reverse().toString();
}

Python Implementation:

def removeDuplicates(S):
    stack = []

    # Traverse each character in the string
    for c in S:
        # Remove adjacent duplicates by popping the stack
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)  # Otherwise, push the character onto the stack

    # Reconstruct the result string from the stack
    return ''.join(stack)

C++ Implementation:

#include 
#include 
using namespace std;

string removeDuplicates(string S) {
    stack stack;

    // Traverse each character in the string
    for (char c : S) {
        // Remove adjacent duplicates by popping the stack
        if (!stack.empty() && stack.top() == c)
            stack.pop();
        else
            stack.push(c); // Otherwise, push the character onto the stack
    }

    // Reconstruct the result string from the stack
    string result;
    while (!stack.empty()) {
        result += stack.top();
        stack.pop();
    }

    // Reverse the result since characters are added in reverse order
    reverse(result.begin(), result.end());
    return result;
}