Algorithms to Remove All Adjacent Duplicates In a String

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”.

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

Please note that every time, we need to remove two duplicates, therefore “aaa” after duplicates removed will become “a” instead of empty string. There are a few ways to doing this.

Two Pointer Algorithm to Remove Adjacent Duplicates In a String

If we have two pointers: one fast and one slow. The fast pointer will be the current character being checked. And the slow pointer will be the valid character (non-duplicate). We can replace the string in-place and the final string will be from the begining to the slow pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    string removeDuplicates(string S) {
        int slow = 0;
        for (int fast = 0; fast < S.size(); ++ fast) {
            if ((slow == 0) || S[slow - 1] != S[fast]) {
                S[slow ++] = S[fast];
            } else {
                slow --;
            }
        }
        return S.substr(0, slow);
    }
};

class Solution {
public:
    string removeDuplicates(string S) {
        int slow = 0;
        for (int fast = 0; fast < S.size(); ++ fast) {
            if ((slow == 0) || S[slow - 1] != S[fast]) {
                S[slow ++] = S[fast];
            } else {
                slow --;
            }
        }
        return S.substr(0, slow);
    }
};

Time complexity O(N) and space complexity O(1).

Using Stack to Remove Adjacent Duplicates In a String

By using a stack, we can peek the top of the stack and check if it is equals to the current character. We push the character if it does not equal to the top of the stack (previous adjacent character) or pop it from the stack – which is to remove the two duplicate characters.

Finally, we just need to pop the remaindering characters in the stack and concatenate them into a string in the reverse order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (const auto &n: S) {
            if (st.empty()) {
                st.push(n);
            } else if (st.top() == n) {
                st.pop();
            } else {
                st.push(n);
            }
        }
        string s = "";
        while (!st.empty()) {
            s = st.top() + s;
            st.pop();
        }
        return s;
    }
};

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (const auto &n: S) {
            if (st.empty()) {
                st.push(n);
            } else if (st.top() == n) {
                st.pop();
            } else {
                st.push(n);
            }
        }
        string s = "";
        while (!st.empty()) {
            s = st.top() + s;
            st.pop();
        }
        return s;
    }
};

Space complexity O(N) by using a stack and the time complexity is O(N).

Using Recursion to Adjacent Duplicates In a String

We search from the begining of the string for duplicate adjacent characters, if we find them, we remove them and recursively call the function until no more duplicates are found.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    string removeDuplicates(string S) {
        for (int i = 1; i < S.size(); ++ i) {
            if (S[i] == S[i - 1]) {
                return removeDuplicates(S.substr(0, i - 1) + 
                                        S.substr(i + 1));
            }
        }
        return S;
    }
};

class Solution {
public:
    string removeDuplicates(string S) {
        for (int i = 1; i < S.size(); ++ i) {
            if (S[i] == S[i - 1]) {
                return removeDuplicates(S.substr(0, i - 1) + 
                                        S.substr(i + 1));
            }
        }
        return S;
    }
};

The recursion gives a clean implementation with O(N) in time and space. Another recursive implementation in Python is below. We use list(string) to convert a String in Python to a char Array. And we use list.pop() to remove an element from the list for given index.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def removeDuplicates(self, S: str) -> str:
        chr = list(S)
        cnt = 0
        i = len(chr) - 1
        while i > 0:
            if chr[i] == chr[i - 1]:
                cnt += 1
                chr.pop(i)
                chr.pop(i - 1)
                i -= 2
            else:
                i -= 1
        if cnt > 0: # until we can't find any duplicates.
            return self.removeDuplicates(''.join(chr))
        return ''.join(chr)            

class Solution:
    def removeDuplicates(self, S: str) -> str:
        chr = list(S)
        cnt = 0
        i = len(chr) - 1
        while i > 0:
            if chr[i] == chr[i - 1]:
                cnt += 1
                chr.pop(i)
                chr.pop(i - 1)
                i -= 2
            else:
                i -= 1
        if cnt > 0: # until we can't find any duplicates.
            return self.removeDuplicates(''.join(chr))
        return ''.join(chr)            

However, if we remove one pair of duplicates and call recursion, it will be a lot slower:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def removeDuplicates(self, S: str) -> str:
        chr = list(S)
        cnt = 0
        for i in range(len(chr) - 1):
            if chr[i] == chr[i + 1]:
                cnt += 1
                chr.pop(i)
                chr.pop(i)
                break
        if cnt == 1:
            return self.removeDuplicates(''.join(chr))
        return ''.join(chr)            

class Solution:
    def removeDuplicates(self, S: str) -> str:
        chr = list(S)
        cnt = 0
        for i in range(len(chr) - 1):
            if chr[i] == chr[i + 1]:
                cnt += 1
                chr.pop(i)
                chr.pop(i)
                break
        if cnt == 1:
            return self.removeDuplicates(''.join(chr))
        return ''.join(chr)            

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

–EOF (The Ultimate Computing & Technology Blog) —