Follow

Follow
1209. Remove All Adjacent Duplicates in String II

1209. Remove All Adjacent Duplicates in String II

An example of using a std::vector as a std::stack

Nhut Nguyen's photo
Nhut Nguyen
·Jan 9, 2023·

3 min read

Problem statement

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and the same 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 1

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There is 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.

Solution: Strings of adjacent equal letters

Construct a stack of strings that has adjacent equal letters and perform the removal during building those strings.

Example 2

For s = "deeedbbcccbdaa" and k = 3:

  • The first built string is "d".

  • Then "eee" with exact length k, remove this string.

  • The next character is 'd', which equals the last character of the last string "d", merge them together. The first string becomes "dd".

  • The next string is "bb".

  • Then "ccc" is removed.

  • The next character 'b' is merged with the last string ("bb") to become "bbb" and be removed.

  • The next character 'd' is merged with the last string ("dd") to become "ddd" and be removed.

  • The remaining string is "aa".

Code

#include <iostream>
#include <vector>
using namespace std;
string removeDuplicates(string s, int k) {
    vector<string> stk;
    int i = 0;
    while (i < s.length()) {
        string a;   // to store adjacent equal letters        
        // perform the merge
        if (!stk.empty() && s[i] == stk.back().back()) {
            a = move(stk.back());
            stk.pop_back();
        }
        int j = i;
        while (j < s.length() && s[j] == s[i]) {
            a += s[j];
            // remove the k-duplicate
            if (a.length() == k) {
                a = "";
            }
            j++;
        }
        if (!a.empty()) {
            stk.push_back(a);
        }
        i = j;
    }
    s = "";
    for (auto& str : stk) {
        s += str;
    }
    return s;
}
int main() {
    cout << removeDuplicates("abcd", 2) << endl;
    cout << removeDuplicates("deeedbbcccbdaa", 3) << endl;
    cout << removeDuplicates("pbbcggttciiippooaais", 2) << endl;
}
abcd
aa
ps

Complexity

  • Runtime: O(N), where N = s.length.

  • Extra space: O(N).

Implementation notes

The data structure stk you might need to solve this problem is a stack. But here are the reasons you had better use std::vector:

  • std::vector has also methods push_back(value) and pop_back() like the ones in stack.

  • On the other hand, it is faster for a vector to perform the string concatenation at the end.

References

Thanks for reading! Feel free to share your thought and get my FREE book "10 Classic Coding Challenges".

Did you find this article valuable?

Support LeetSolve by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this