Stack is particularly adept at solving matching problems.

1047. Remove All Adjacent Duplicates In String

Link to the LeetCode problem (opens new window)

Given a string S of lowercase letters, a duplicate removal operation will choose two adjacent and equal letters and remove them.

We repeatedly perform duplicate removal operations on S until we can no longer do so.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example:

• Input: "abbaca"
• Output: "ca"
• Explanation: For example, in "abbaca", we can remove "bb" because the letters are adjacent and equal. This is the only possible removal step at this point. After that, we get the string "aaca", from which only "aa" can be removed, leading to the final string "ca".

Constraints:

• 1 <= S.length <= 20000
• S consists only of lowercase English letters.

Thought Process

Main Solution

This problem requires removing adjacent duplicate elements, similar to 20. Valid Parentheses (opens new window) which is about matching pairs of parentheses, except this problem is about matching adjacent elements to perform removals. Both problems involve elimination operations.

This is another classic problem solved using a stack.

So, what elements should be placed in the stack?

When removing adjacent duplicates, we need to know if the current element being traversed has a similar element traversed in the previous position. How do we record the elements that have been traversed?

This is where a stack comes in handy. The purpose of the stack is to store elements that have been traversed. As we traverse the current element, we check in the stack to see if there is an adjacent element with the same value.

Then, perform the corresponding elimination operation, as shown in the animation:

Pop the remaining elements from the stack; the resulting string is "ac". Since the elements popped from the stack are in reverse order, reversing the string yields the final result.

C++ code:

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s and st.top() are equal
            }
        }
        string result = "";
        while (!st.empty()) { // Transfer stack elements to result string
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end()); // Reverse the string at this point
        return result;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(n)

Alternatively, the string itself can be used as a stack, avoiding the need to convert the stack back into a string.

Code is as follows:

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1), excluding the space for the return value

Additional Thoughts

This problem is similar to games like "match-3", where adjacent similar elements need to be removed.

While playing such a game, it may seem intuitive that adjacent elements should be eliminated, but how does a program know when to eliminate, especially when new elements could come together after an elimination?

In such cases, the backend logic of games can use a stack to achieve this, not unlike in programming languages where stacks implement function recursive calls (Note: Not all programming languages support recursion).

Recursion is implemented by pushing local variables, parameter values, and return addresses of a function call onto the call stack, and then during recursion return, popping the parameters of the last recursive call, which explains how recursion can return to the previous layer position.

You might have encountered a stack overflow error, indicated by a Segmentation fault exception (although not every Segmentation fault is caused by a stack overflow), and if you are using recursion, it's worth considering whether there is infinite recursion, causing the system call stack to overflow.

Moreover, try to avoid using recursion as much as possible in enterprise-level project development! When the projects grow larger, due to many parameters and global variables, using recursion can easily lead to insufficient return conditions, making it very easy to cause infinite recursion (or recursion levels too deep), resulting in stack overflow errors (which can be difficult to debug!).

Versions in Other Languages

Java:

Using Deque as a stack

class Solution {
    public String removeDuplicates(String S) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

Using the string directly as a stack to avoid additional conversion.

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer res = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

Alternative: Two pointers

public class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            ch[slow] = ch[fast];
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}

Python:

# Method 1: Using a stack
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)

# Method 2: Using two pointers to simulate a stack. This can be an alternative if a stack is not allowed.
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        slow = fast = 0
        length = len(res)

        while fast < length:
            res[slow] = res[fast]
            
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
            
        return ''.join(res[0: slow])

Go:

Using a stack

func removeDuplicates(s string) string {
    stack := make([]rune, 0)
    for _, val := range s {
        if len(stack) == 0 || val != stack[len(stack)-1] {
            stack = append(stack, val)
        } else {
            stack = stack[:len(stack)-1]
        }
    }
    var res []rune
    for len(stack) != 0 {
        res = append(res, stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    l, r := 0, len(res)-1
    for l < r {
        res[l], res[r] = res[r], res[l]
        l++
        r--
    }
    return string(res)
}

Using a string directly as a stack to avoid extra conversion.

func removeDuplicates(s string) string {
    var stack []byte
    for i := 0; i < len(s);i++ {
        if len(stack) > 0 && stack[len(stack)-1] == s[i] {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

JavaScript:

Method 1: Using a stack

var removeDuplicates = function(s) {
    const result = []
    for(const i of s){
        if(i === result[result.length-1]){
            result.pop()
        }else{
            result.push(i)
        }
    }
    return result.join('')
};

Method 2: Using two pointers (simulated stack)

// In-place method (simulate stack with two pointers)
var removeDuplicates = function(s) {
    s = [...s];
    let top = -1; // stack top index
    for(let i = 0; i < s.length; i++) {
        if(top === -1 || s[top] !== s[i]) {
            s[++top] = s[i];
        } else {
            top--;
        }
    }
    s.length = top + 1;
    return s.join('');
};

TypeScript:

function removeDuplicates(s: string): string {
    const helperStack: string[] = [];
    let i: number = 0;
    while (i < s.length) {
        let top: string = helperStack[helperStack.length - 1];
        if (top === s[i]) {
            helperStack.pop();
        } else {
            helperStack.push(s[i]);
        }
        i++;
    }
    let res: string = '';
    while (helperStack.length > 0) {
        res = helperStack.pop() + res;
    }
    return res;
};

C:

Method 1: Using a stack

char * removeDuplicates(char * s){
    int strLength = strlen(s);
    char* stack = (char*)malloc(sizeof(char) * strLength + 1);
    int stackTop = 0;

    int index = 0;
    while(index < strLength) {
        char letter = s[index++];
        if(stackTop > 0 && letter == stack[stackTop - 1])
            stackTop--;
        else
            stack[stackTop++] = letter;
    }
    stack[stackTop] = '\0';
    return stack;
}

Method 2: Two pointers

char * removeDuplicates(char * s){
    int fast = 0;
    int slow = 0;
    int strLength = strlen(s);
    while(fast < strLength) {
        char letter = s[slow] = s[fast++];
        if(slow > 0 && letter == s[slow - 1])
            slow--;
        else
            slow++;
    }
    s[slow] = 0;
    return s;
}

Swift:

func removeDuplicates(_ s: String) -> String {
    var stack = [Character]()
    for c in s {
        if stack.last == c {
            stack.removeLast()
        } else {
            stack.append(c)
        }
    }
    return String(stack)
}

C#:

public string RemoveDuplicates(string s) {
        StringBuilder res = new StringBuilder();

        foreach(char c in s){
            if(res.Length > 0 && res[res.Length-1] == c){
                res.Remove(res.Length-1, 1);
            }else{
                res.Append(c);
            }
        }
       
        return res.ToString();
    }

PHP:

class Solution {
    function removeDuplicates($s) {
        $stack = new SplStack();
        for($i=0;$i<strlen($s);$i++){
            if($stack->isEmpty() || $s[$i] != $stack->top()){
                $stack->push($s[$i]);
            }else{
               $stack->pop(); 
            }
        }

        $result = "";
        while(!$stack->isEmpty()){
            $result.= $stack->top();
            $stack->pop();
        }
        
        return strrev($result);
    }
}

Scala:

object Solution {
  import scala.collection.mutable
  def removeDuplicates(s: String): String = {
    var stack = mutable.Stack[Int]()
    var str = ""
    for (i <- s.indices) {
      var tmp = s(i)
      if (!stack.isEmpty && tmp == stack.head) {
        str = str.take(str.length - 1)
        stack.pop()
      } else {
        stack.push(tmp)
        str += tmp
      }
    }
    str
  }
}

Rust:

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut stack = vec![];
        let mut chars: Vec<char> = s.chars().collect();
        while let Some(c) = chars.pop() {
            if stack.is_empty() || stack[stack.len() - 1] != c {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        stack.into_iter().rev().collect()
    }
}

Ruby

def remove_duplicates(s)
  stack = []
  s.each_char do |chr|
    if stack.empty?
      stack.push chr
    else
      head = stack.pop 
      stack.push head, chr if head != chr
    end
  end

  return stack.join
end