diff options
Diffstat (limited to 'other/remove_adjacent_dup.cpp')
-rw-r--r-- | other/remove_adjacent_dup.cpp | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/other/remove_adjacent_dup.cpp b/other/remove_adjacent_dup.cpp new file mode 100644 index 0000000..c0cc341 --- /dev/null +++ b/other/remove_adjacent_dup.cpp @@ -0,0 +1,37 @@ +#include "leetcode.h" + +class Solution { +public: + string removeDuplicates(string s, int k) { + // cout << s << endl << k << endl; + if (s.size() < k) + return s; + stack<pair<char, int>> stk; + for (int i = 0; i < s.size(); ++i) { + if (stk.empty() || stk.top().first != s[i]) + stk.push({s[i], 1}); + else { + auto prev = stk.top(); + stk.pop(); + stk.push({s[i], prev.second + 1}); + } + if (stk.top().second == k) + stk.pop(); + } + string ans = ""; + while (!stk.empty()) { + auto curr = stk.top(); + stk.pop(); + while (curr.second--) + ans.push_back(curr.first); + } + reverse(ans.begin(), ans.end()); + // cout << ans; + return ans; + } +}; + +int main() { + Solution obj; + obj.removeDuplicates("deeedbbcccbdaa", 3); +} |