1209. Remove All Adjacent Duplicates in String II | LeetCode Solution
You are given a string s
and an integer k
, 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.
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 <= 105
2 <= k <= 104
s
only contains lower case English letters.
class Solution {
public:
string removeDuplicates(string s, int k) {
stack<pair<char,int>>st;
for(int i=0; i<s.length(); i++){
if(st.empty()){
st.push({s[i],1});
}
else {
if(st.top().first==s[i]){
st.top().second++;
if(st.top().second==k){
st.pop();
}
}
else{
st.push({s[i],1});
}
}
}
string ans="";
// cout<<st.size();
while(!st.empty()){
while(!st.empty() && st.top().second!=0){
ans+=st.top().first;
st.top().second--;
// cout<<st.top().second<<endl;
if(st.top().second==0)
st.pop();
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.