Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Remove All Adjacent Duplicates In String
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

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

Examples

    • Input: s = "abccba"
    • Output: ""
    • Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
    • Input: s = "foobar"
    • Output: "fbar"
    • Explanation: We remove "oo" to get "fbar".
    • Input: s = "fooobar"
    • Output: "fobar"
    • Explanation: We remove the pair "oo" to get "fobar".
    • Input: s = "abcd"
    • Output: "abcd"
    • Explanation: No adjacent duplicates so no changes.

Constraints:

  • 1 <= s.length <= 10<sup>5</sup>
  • s consists of lowercase English letters.

Solution

This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.

Algorithm Walkthrough

  1. Initialize an empty stack.
  2. Loop through the characters in the given string s.
  3. For each character:
    • If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
    • Otherwise, push the current character onto the stack.
  4. Finally, build the result string from the characters remaining on the stack.
Image

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time and Space Complexity

The time complexity of this algorithm is O(N), where N is the length of s, because we perform one operation per character in s. The space complexity is also O(N), as in the worst case, every character in s is pushed onto the stack.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible