[LeetCode] Remove All Adjacent Duplicates in String II

Problem: You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Approach: This problem is same as the problem Remove All Adjacent Duplicates In String. If you look closely in the previous problem k is always 2. We will use stack to solve this problem too. Here we won't just push the character but also we need to maintain the current continuous count of the character so if we see the character at the top is same as the current character, we increase its count and if we see the count is same as k then we pop that means we need to push a pair of character and it's count in stack. If the characters are not same then we safely push the pair of current character and 1(current count).

We can solve it without using stack to like we did before however I don't see much of benefit here as we need to maintain a count array anyways so extra storage will be there. I have given this implementation too. 

Implementation in C#:

Using Stack:

    public string RemoveDuplicates(string s, int k)

    {

        int length = s?.Length ?? 0;

        if (length < k)

        {

            return s;

        }

        var stack = new Stack<KeyValuePair<char, int>>();

        foreach (char ch in s)

        {

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

            {

                stack.Push(new KeyValuePair<char, int>(ch, 1));

            }

            else

            {

                var stElem = stack.Pop();

                if (stElem.Value < k - 1)

                {

                    stack.Push(new KeyValuePair<char, int>(ch, stElem.Value + 1));

                }

            }

        }

        if (stack.Count == 0)

        {

            return "";

        }

        StringBuilder result = new StringBuilder();

        while (stack.Count != 0)

        {

            var stElem = stack.Pop();

            for (int i = 0; i < stElem.Value; ++i)

            {

                result.Append(stElem.Key);

            }

        }

        return new string(result.ToString().Reverse().ToArray());

    }

Without using stack:

    public string RemoveDuplicates(string s, int k)

    {

        int length = s?.Length ?? 0;

        if (length < k)

        {

            return s;

        }

        char[] stack = s.ToCharArray();

        int[] count = new int[stack.Length];

        int stackTop = -1;

        foreach (char ch in s)

        {

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

            {

                stack[++stackTop] = ch;

                count[stackTop] = 1;

            }

            else

            {

                if (count[stackTop] < k - 1)

                {

                    ++count[stackTop];

                }

                else

                {

                    --stackTop;

                }

            }

        }

        if (stackTop == -1)

        {

            return "";

        }

        StringBuilder result = new StringBuilder();

        for (int i = 0; i <= stackTop; ++i)

        {

            for (int j = 0; j < count[i]; ++j)

            {

                result.Append(stack[i]);

            }

        }

        return result.ToString();

    }

Complexity: O(n)