[LeetCode] Remove All Adjacent Duplicates In String

Problem: 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. It can be proven that the answer is unique.

Example:

Input: s = "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".

Input: s = "azxxzy"
Output: "ay"

Approach: We can use stack to solve this problem as we need to repeatedly remove duplicates. The solution is simple; We iterate through the input string s, if the top of the stack matches with the current character, we just pop otherwise we push current character into stack. Once the loop is completed, we can take all the characters from the stack into a string and reverse it. That will be our answer.

The above apporach works and is very efficient, but if you see we are using extra storage in the form of stack. Can we do better?

We can use our result string as stack. We just need to recall how to implement stack using an array and in that way we will be able to save space.

That's all!

Implementation in C#:

Using Stack:

    public string RemoveDuplicates(string s)

    {

        int length = s?.Length ?? 0;

        if (length <= 1)

        {

            return s;

        }

        Stack<char> stack = new Stack<char>();

        foreach(char ch in s)

        {

            if (stack.Count == 0 || stack.Peek() != ch)

            {

                stack.Push(ch);

            }

            else

            {

                stack.Pop();

            }

        }

        if (stack.Count == 0)

        {

            return "";

        }

        char[] result = new char[stack.Count];

        int index = stack.Count - 1;

        while (stack.Count != 0)

        {

            result[index--] = stack.Pop();

        }

        return new string(result);

    }

Without using stack:

        public string RemoveDuplicates(string s)

    {

        int length = s?.Length ?? 0;

        if (length <= 1)

        {

            return s;

        }

        char[] result = s.ToCharArray();

        int stackTop = -1;

        foreach(char ch in s)

        {

            if (stackTop == -1 || result[stackTop] != ch)

            {

                result[++stackTop] = ch;

            }

            else

            {

                --stackTop;

            }

        }

        if (stackTop == -1)

        {

            return "";

        }

        return new string(result, 0, stackTop + 1);

    }

Complexity: In both the cases O(n)