Dec 133 min read

LeetCode - Remove All Adjacent Duplicates In String

Updated: Dec 14

Today lets solve yet another leetcode question Remove All Adjacent Duplicates In String. This article is part of our leetcode problem solutions series, so be sure to explore other articles in this series after you are done with this problem.

Let's now jump to the problem statement.

Problem Statement: Remove All Adjacent Duplicates In String

We are given a string s consisting of lower case English letters. Write an algorithm that removes two same/equal adjacent letters from this string. Your algorithm should repeatedly remove all such adjacent duplicate letters from s until none are left.

Return the final string after all such duplicate removals have been made.

Example 1:

Input: s = "abccba"
Output: ""
Explanation: Here we first remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.

Solution

If you encounter such questions involving removing characters from a given input string based on certain conditions, there is a good chance that this problem can be solved using a stack. Because problems involving such a pattern can be efficiently solved using stack in most cases. We will be using the stack approach here as well to solve this question. Below is a step by step explanation of how this algorithm works:

Algorithm

To begin with, initialize an empty stack (you can choose to use an array that acts like a stack for this purpose).
Next, iterate through the characters of the given input string one by one.
In each iteration, you do the following things:
1. If the stack is empty or if the top element in the stack is not the same as the current element (in our iteration), add the current element to the stack.
2. Otherwise (if stack is not empty and top element in stack is same as the current element), pop the top element from the stack (since we have found a duplicate).
Continue step 2 & 3 until we reach the end of string s.
Finally, return whatever characters are left in the stack as the result.

Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses:

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Complexity Analysis

Time Complexity

This algorithm uses a loop to iterate over the characters in the given string once which has a time complexity of O(n), where n is the length of the given input string. And in each iteration we perform constant time, operations like pushing/popping elements from the stack which has a time complexity of O(1). Therefore, the overall time complexity of this algorithm is O(n) + O(1) = O(n).

Space Complexity

Since we are using a stack here, and in the worst case we might end up storing all elements of s in the stack (this happens when all characters in s are unique), the space complexity is O(n).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.