DEV Community

Cover image for Solution: Remove All Adjacent Duplicates in String II
seanpgallivan
seanpgallivan

Posted on • Updated on

Solution: Remove All Adjacent Duplicates in String II

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #1209 (Medium): Remove All Adjacent Duplicates in String II


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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 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.


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.

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)



(Jump to: Problem Description || Solution Idea)

(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)


Idea:

Whenever we have to iterate through a data type and remove potentially nested information, the natural thought is to use some kind of stack or recursive solution to keep track of the nesting data while we search for our matches.

In a naive recursive solution, we can search for a pattern match by keeping track of the current count of adjacent duplicates, then recursively call the main function again on the string with the pattern removed. This solution repeatedly iterates through most of the string, but otherwise has low overhead, so it tends to be competitively performant, especially for shorter strings.

(Note: With the addition of some more complex tests to the testing suite, the less-efficient recursive solution no longer passes without a TLE result. The following in-place stack solution is much better and continues to work. I'll leave the previous paragraph in place, but I'm removing the code below for the recursive solutions.)

In an effort to achieve a more efficient solution for longer strings, we can instead use a stack to build our answer. To avoid having to backtrack up to the last K elements of our stack after removing a match, we can keep a separate stack (st) just specifically for index values of the start of each duplicate run.

To save on space, we can also use an in-place stack approach for the char array (SC) formed from the input string (S), rather than using a separate stack. To do so, we can use a two-pointer system in which one pointer (i) keeps track of the end of the in-place "stack", while the other pointer (j) iterates through SC normally.

As we move j through SC, we write to the "stack" by overwriting SC[i] with SC[j]. When we want to remove K elements from the "stack", we just move i back by K. Then, once we're done, we can return the "stack", which is the first part of SC through i.

This solution has more overhead, but won't repeat as many iterations, so it should be more efficient for longer strings.

In-place stack example: S = "aabbbcdddcc", K = 3

         i,j                             // i, j start at 1
S  = [ a, A, b, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0 ]                               // S[i] == S[i-1], no change


          ->i,j                          // i, j move up 1
S  = [ a, a, B, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] != S[i-1], st.push(i)


             ->i,j                       // i, j move up 1
S  = [ a, a, b, B, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


                ->i,j                    // i, j move up 1
S  = [ a, a, b, b, B, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


          i<-------j                     // i moves back because...
S  = [ a, a, B--B--B, c, d, d, d, c, c ] // ...3 b's found, so...
st = [ 0 ]                               // ...i = st.pop() - 1


           ->i      ->j                  // i, j move up 1
S  = [ a, a, C<-------C, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // new letter, st.push(i)


              ->i      ->j               // i, j move up 1
S  = [ a, a, c, D<-------D, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // new letter, st.push(i)


                 ->i      ->j            // i, j move up 1
S  = [ a, a, c, d, D<-------D, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // S[i] == S[i-1], no change


                    ->i      ->j         // i, j move up 1
S  = [ a, a, c, d, d, D<-------D, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // S[i] == S[i-1], no change


             i<--------        j         // i moves back because...
S  = [ a, a, c, D--D--D,  ,  ,  , c, c ] // ...3 d's found, so...
st = [ 0, 2 ]                            // ...i = st.pop() - 1


              ->i               ->j      // i, j move up 1
S  = [ a, a, c, C<----------------C, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


                 ->i               ->j   // i, j move up 1
S  = [ a, a, c, c, C<----------------C ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


          i<--------                 j   // i moves back because...
S  = [ a, a, C--C--C,  ,  ,  ,  ,  ,   ] // ...3 c's found, so...
st = [ 0 ]                               // ...i = st.pop() - 1


S  = [ a, a ]                            // only keep S up to i
   = "aa"                                // then join to a string
Enter fullscreen mode Exit fullscreen mode
  • Time Complexity: O(N) for iterating through the input string
  • Space Complexity:
    • O(N) (JS, Python, Java): for converting the string to an array for in-place modification
    • O(1) (C++): because C++ has mutable strings

Implementation:

C++ alone has mutable strings and doesn't require S to be split into a char array before processing as an in-place stack.


Javascript Code:


(Jump to: Problem Description || Solution Idea)

w/ Recursion:
  • Time Limit Exceeded
w/ In-Place Stack:
var removeDuplicates = function(S, K) {
    let SC = S.split(""), st = [0], i, j
    for (i = 1, j = 1; j < S.length; SC[++i] = SC[++j]) {
        if (SC[i] !== SC[i-1]) st.push(i)
        else if (i - st[st.length-1] + 1 === K) i = st.pop()-1
    }
    return SC.slice(0,i+1).join("")
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

w/ Recursion:
  • Time Limit Exceeded
w/ In-Place Stack:
class Solution:
    def removeDuplicates(self, S: str, K: int) -> str:
        SC, st, i, j = list(S), [0], 1, 1
        while j < len(S):
            SC[i] = SC[j]
            if i == 0 or SC[i] != SC[i-1]: st.append(i)
            elif i - st[-1] + 1 == K: i = st.pop() - 1
            i += 1
            j += 1
        return "".join(SC[:i])
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

w/ Recursion:
  • Time Limit Exceeded
w/ In-Place Stack:
class Solution {
    public String removeDuplicates(String S, int K) {
        char[] SC = S.toCharArray();
        int i, j;
        Stack<Integer> st = new Stack<>();
        st.add(0);
        for (i = 1, j = 1; j < S.length(); i++, j++) {
            char chr = SC[i] = SC[j];
            if (i == 0 || chr != SC[i-1]) st.add(i);
            else if (i - st.peek() + 1 == K) i = st.pop() - 1;
        }
        return new String(SC, 0, i);
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

w/ Recursion:
  • Time Limit Exceeded
w/ In-Place Stack:
class Solution {
public:
    string removeDuplicates(string S, int K) {
        int i, j;
        stack<int> st;
        st.push(0);
        for (i = 1, j = 1; j < S.size(); i++, j++) {
            S[i] = S[j];
            if (i == 0 || S[i] != S[i-1]) st.push(i);
            else if (i - st.top() + 1 == K) {
                i = st.top() - 1;
                st.pop();
            }
        }
        return S.substr(0, i);
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (7)

Collapse
 
spartan1cs profile image
spartan1cs

Not able to imagine stack approach in java
very difficult to do dry run

Collapse
 
seanpgallivan profile image
seanpgallivan

Here's an example, hopefully it helps!

// Example: S = "aabbbcdddcc", K = 3


         i,j                             // i, j start at 1
S  = [ a, A, b, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0 ]                               // S[i] == S[i-1], no change


          ->i,j                          // i, j move up 1
S  = [ a, a, B, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] != S[i-1], st.push(i)


             ->i,j                       // i, j move up 1
S  = [ a, a, b, B, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


                ->i,j                    // i, j move up 1
S  = [ a, a, b, b, B, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change
          i<-------j                     // i moves back because...
S  = [ a, a, B--B--B, c, d, d, d, c, c ] // ...3 b's found, so...
st = [ 0 ]                               // ...i = st.pop() - 1


           ->i      ->j                  // i, j move up 1
S  = [ a, a, C<-------C, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // new letter, st.push(i)


              ->i      ->j               // i, j move up 1
S  = [ a, a, c, D<-------D, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // new letter, st.push(i)


                 ->i      ->j            // i, j move up 1
S  = [ a, a, c, d, D<-------D, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // S[i] == S[i-1], no change


                    ->i      ->j         // i, j move up 1
S  = [ a, a, c, d, d, D<-------D, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ]                         // S[i] == S[i-1], no change
             i<--------        j         // i moves back because...
S  = [ a, a, c, D--D--D,  ,  ,  , c, c ] // ...3 d's found, so...
st = [ 0, 2 ]                            // ...i = st.pop() - 1


              ->i               ->j      // i, j move up 1
S  = [ a, a, c, C<----------------C, c ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change


                 ->i               ->j   // i, j move up 1
S  = [ a, a, c, c, C<----------------C ] // S[j] overwrites S[i]
st = [ 0, 2 ]                            // S[i] == S[i-1], no change
          i<--------                 j   // i moves back because...
S  = [ a, a, C--C--C,  ,  ,  ,  ,  ,   ] // ...3 c's found, so...
st = [ 0 ]                               // ...i = st.pop() - 1


S  = [ a, a ]                            // only keep S up to i
   = "aa"                                // then join to a string
Enter fullscreen mode Exit fullscreen mode
Collapse
 
spartan1cs profile image
spartan1cs • Edited

wow thanks :)
I got it

Collapse
 
filatovv profile image
Yuri Filatov

Very good work

Collapse
 
seanpgallivan profile image
seanpgallivan

Thanks!

Collapse
 
adithyashan11 profile image
Adithya Shankaran

the recursion method used in the c++ code with exceed the memory limit

Collapse
 
seanpgallivan profile image
seanpgallivan

As more tests were added to the testing suite on leetcode, it pushed the less efficient solution to TLE, as you noticed.

Updated the solution to remove the recursion solution, as the in-place stack solution was better, anyway.