Apply your skills to use stacks for various tasks, including calculators, string manipulation, and queuing.

Coding

Operates on a last-in, first-out principle, where elements are added and removed from the same end, facilitating ordered data processing and retrieval.

Stacks

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# Statement
You are given a string consisting of lowercase English letters. Repeatedly remove adjacent duplicate letters, one pair at a time. Both members of a pair of adjacent duplicate letters need to be removed.

**Constraints:**
* $1 \leq$ `string.length` $\leq 10^3$
* `string` consists of lowercase English alphabets.

# Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
## Naive approach

The naive approach is to generate a set of all possible adjacent duplicates in a string of small English alphabets, that is, `{"aa", "bb", "cc", "dd", ...}`. Traverse over the string to see if such duplicates are present. We'll use nested loops to check this condition. If duplicate characters are found, we'll remove the adjacent duplicates from the input string. For example, in the `"abaac"` string, we'll remove `"aa"` from the string, which results in `"abc"`.


Since we're using nested loops, the time complexity of this approach is $O(n^2)$, which is not optimal. Let’s see if we can use the stacks pattern to reduce the time complexity of our solution.

## Optimized approach using stacks

We can remove adjacent duplicates in pairs, which is similar to matching opening and closing parentheses. In such problems, we typically use stacks to store intermediate results to deal with nested pairs of parentheses. We'll use the same concept here.

We'll initialize a stack first. Then, we'll iterate the complete string from left to right, and for every character, we'll check the following:

- If the stack is empty, we'll push the character onto the stack.
- If the stack is not empty, we'll perform the following tasks:
  - If the string's character is different from the stack's top character, we'll push the string's character onto the stack because we did not find the adjacent duplicate.
  - If the string's character is the same as the stack's top character, it means that we found the adjacent duplicate characters. We'll pop that character from the stack and move to the next character in the string.
- After the entire string has been traversed, the remaining characters in the stack will be our result. We'll form a string from those characters and return it.

The slides below illustrate how we’d like the algorithm to run:

Let's solve the Remove All Adjacent Duplicates In String problem using the Stacks pattern.

Solution: Remove All Adjacent Duplicates In String

Statement▼

Solution: Remove All Adjacent Duplicates In String

Statement▼