Teaching Kids Programming – Using a Stack to Remove All Adjacent Duplicates In String

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string S of lowercase 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.  It is guaranteed the answer is unique.

Example 1:
Input: “abbaca”
Output: “ca”
Explanation:
For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.

Recursive Bruteforce Algorithm to Remove All Adjacent Duplicates In String

The bruteforce algorithm works by checking each neigbour characters, if they are same, call itself with those two characters removed. This takes O(N^2) time because in worst cases for input strings like “dcabbacd” even-size palindrome strings, it takes O(N^2) time. Odd-size palindrome strings will not be modified in the process for example: “abcba”

1
2
3
4
5
6

class Solution:
    def removeDuplicates(self, S: str) -> str:
        for i in range(1, len(S)):
            if S[i] == S[i - 1]:
                return self.removeDuplicates(S[:i-1]+S[i+1:])
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        for i in range(1, len(S)):
            if S[i] == S[i - 1]:
                return self.removeDuplicates(S[:i-1]+S[i+1:])
        return S

You might implement it using Non-Recursion, which you have to rewind the pointer everytime you delete two duplicate characters, which virtually make it quadratic time.

Remove All Adjacent Duplicates In String via a Stack

The ideal/optimal solution would be to use an additional stack data structure, pushes each character if it is not the same as the top of the stack. Remove the top of the stack if it matches the next character.

1
2
3
4
5
6
7
8
9

class Solution:
    def removeDuplicates(self, S: str) -> str:
        ans = []
        for i in S:
            if len(ans) and i == ans[-1]:
                ans.pop()
            else:
                ans.append(i)
        return ''.join(ans)

class Solution:
    def removeDuplicates(self, S: str) -> str:
        ans = []
        for i in S:
            if len(ans) and i == ans[-1]:
                ans.pop()
            else:
                ans.append(i)
        return ''.join(ans)

The time complexity is O(N). Space complexity is O(N).

See also: Algorithms to Remove All Adjacent Duplicates In a String

–EOF (The Ultimate Computing & Technology Blog) —