Leetcode: Remove all Adjacent Duplicates in a String II

This is a very common Bloomberg, Roblox, and Facebook Question. It is given a string s, 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 make removals until we no longer are able to. Here are some examples: 

Example 1:

Input: s = "abcd", k = 2

Output: "abcd"

Explanation: There's nothing to delete.

Example 2:

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"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2

Output: "ps"

Constraints:

1 <= s.length <= 10^5

2 <= k <= 10^4

s only contains lower case English letters.

First I want to go over the brute force approach.

Here it is:

Remember the length of the string. Iterate through the string and if the current character is the same, as the one before increase the count, else reset the count to 1. if the count equals k erase it, and repeat starting from first step, depending on whether the length of the string is changed. 

public String removeDuplicates(String s, int k) {

    StringBuilder sb = new StringBuilder(s);

    int length = -1;

    //if the length is not equal, then see now many characters are

    while(length != sb.length()) {

        length = sb.length();

        for(int i = 0, count = 1; i < sb.length; ++i) {

            //iterate through all the strings and count them properly

            if(i == 0 || sb.charAt(i) != sb.charAt(i - 1) count = 1;

            else if (++count = k) {

                sb.delete(i - k + 1, i + 1);

            //if proper count iterate through the while loop and count again

                break;

            }

        }

    }

    //return the stringbuilder

    return sb.toString();

}

O(n^2/K) is the time complexity. They increase the count, and then see if the count is equivalent to k, and delete the corresponding characters if they are. 

Here is another solution, which is backtracking. I believe this is among one of the most efficient solutions.

We can use 2 pointers to optimize operations. We copy characters within the same string using fast and slow pointers.  

We initialize the slow pointer j to and move the fast pointer i through the string. 

Increment the count on top of the stack if s[j] is the same as s[j - 1], otherwise, push 1 to the stack. If the count equals to k decrease j by k and pop from the stack. Then return the j first characters of the string. 

public String removeDuplicates(String s, int k) {

    Stack<Integer> counts = new Stack<>();

    char[] sa = s.toCharArray();

    int j = 0;

    //get the character array

    for(int i = 0; i < s.length; ++i; ++j) {

        sa[j] = sa[i];

        //see if the characters equal, push if they equal

        if(j == 0 || sa[j] != sa[j - 1]) {

            counts.push(1);

        }

    //if these characters are not equal 

     else {

            int incremented = counts.pop() + 1;

            //if there is k incremented, move the characters over to ending

            if(incremented == k) {

                j = j - k;

            } else {

                //else put the character back in here. 

                counts.push(incremented);

            }

        }

    }

    //return the first j characters

    return new String(sa, 0, j);

}