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
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;
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];
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
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".
