Home | Projects | Notes > Problem Solving > LC - E - 1209. Remove All Adjacent Duplicates In String 2 (stack, recursion)

LC - E - 1209. Remove All Adjacent Duplicates In String 2 (stack, recursion)

Solutions in C++

Solution 1

This solution uses STL stack container.

Complexity Analysis:

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

• $S=O(n)$$S = O(n)$ since this solution uses additional memory for stack

Solution:

xxxxxxxxxx
35
1
class Solution {
2
public:
3
    string removeDuplicates(string s, int k) {
4
        stack<pair<char, int> > st; // element type is a pair of character and its count
5
        string ret = "";
6

7
        // stack the characters, leaving non-k-consecutive ones only
8
        for (char ch : s)
9
        {
10
            if (st.empty() || ch != st.top().first)
11
                st.push({ch, 1});
12
            else
13
            {
14
                st.top().second++;          // increment the count
15

16
                if (st.top().second == k)   // check the count
17
                    st.pop();    
18
            }
19
        }
20

21
        // pop the characters out of the stack to build the string to return
22
        while (!st.empty())
23
        {
24
            for (int i = 0; i < st.top().second; i++) // while (st.top().second--)
25
                ret += st.top().first;
26

27
            st.pop();
28
        } // at this point, 'ret' contains the reverse of the string to return
29

30
        // reverse the string 'ret'
31
        reverse(ret.begin(), ret.end());
32

33
        return ret;
34
    }
35
};

Solution 2

This solution uses recursion. (My first solution)

Complexity Analysis:

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

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

Solution:

xxxxxxxxxx
43
1
class Solution {
2
public:
3
    string removeDuplicates(string s, int k) {
4
        string ret;
5
        int count = 1;
6
        bool isComplete = true;
7

8
        for (char ch : s)
9
        {
10
            if (ret.empty())
11
            {
12
                ret.push_back(ch);
13
            }
14
            else
15
            {
16
                if (ch == ret.back())
17
                    ++count;
18
                else
19
                    count = 1;
20

21
                ret.push_back(ch);
22

23
                if (count == k)
24
                {
25
                    isComplete = false;
26

27
                    while (count > 0)
28
                    {
29
                        ret.pop_back();
30
                        count--;
31
                    }
32

33
                    count = 1;
34
                }
35
            }
36
        }
37

38
        if (isComplete) 
39
            return ret;
40

41
        return removeDuplicates(ret, k);
42
    }
43
};