Home | Projects | Notes > Problem Solving > LC - E - 1047. Remove All Adjacent Duplicates In String 1 (stack)

LC - E - 1047. Remove All Adjacent Duplicates In String 1 (stack)

Solutions in C++

Solution 1

This solution uses STL stack container.

The original string does not get modified.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the string

• $S=O(n)$$S = O(n)$

Solution:

xxxxxxxxxx
28
1
class Solution {
2
public:
3
    string removeDuplicates(string s) {
4
        string ret;
5
        stack<char> st;
6

7
        // stack non-adjacent-duplicate characters only
8
        for (char ch : s)
9
        {
10
            if (!st.empty() && ch == st.top())
11
                st.pop();
12
            else
13
                st.push(ch);
14
        }
15

16
        // pop the characters out of the stack to build the string to return
17
        while (!st.empty())
18
        {
19
            ret += st.top();    // ret.push_back(st.top());
20
            st.pop();
21
        } // at this point, 'ret' contains the reverse of the string to return
22

23
        // reverse the string 'ret'
24
        reverse(ret.begin(), ret.end());
25

26
        return ret;
27
    }
28
};

Solution 2

This solution uses STL stack container.

The original string gets modified.

Be careful when using the member function erase(). Following statement will erase everything from s[i] on:

xxxxxxxxxx
1
1
s.erase(i);

I had to spend quite some time debugging it.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the string

• $S=O(n)$$S = O(n)$

Solution:

xxxxxxxxxx
22
1
class Solution {
2
public:
3
    string removeDuplicates(string s) {
4
        int i = 0;
5
        stack<char> st;
6

7
        while (i < s.size())
8
        {          
9
            if (!st.empty() && s[i] == st.top())
10
            {
11
                st.pop();
12
                s.erase(i--, 1);
13
                s.erase(i, 1);
14
                continue;
15
            }
16

17
            st.push(s[i]);            
18
            ++i;
19
        }
20
        return s;
21
    }
22
};  

Solution 3

This solution solves the problem without using the STL stack container. Instead, a string object is used to build up the string to return.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the string

• $S=O(n)$$S = O(n)$

Solution:

xxxxxxxxxx
15
1
class Solution {
2
public:
3
    string removeDuplicates(string s) {
4
        string ret;
5

6
        for (char ch : s)
7
        {
8
            if (!ret.empty() && ret.back() == ch)
9
                ret.pop_back();
10
            else
11
                ret += ch;
12
        }
13
        return ret;
14
    }
15
};