LeetCode 솔루션 분류
[5/6] 1209. Remove All Adjacent Duplicates in String II
본문
[LeetCode 시즌 3] 2022년 5월 6일 문제입니다.
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
[Medium] 1209. Remove All Adjacent Duplicates in String II
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.
태그
#LeetCode, #Bloomberg, #Facebook, #Amazon, #Goldman Sachs, #Apple, #Spotify, #Visa, #String, #Stack
관련자료
-
링크
댓글 2
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 26 ms, faster than 66.98% of C++ online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: 10.9 MB, less than 36.43% of C++ online submissions for Remove All Adjacent Duplicates in String II.
Runtime: 26 ms, faster than 66.98% of C++ online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: 10.9 MB, less than 36.43% of C++ online submissions for Remove All Adjacent Duplicates in String II.
class Solution {
public:
string removeDuplicates(string s, int k) {
stack<pair<char, int>> st;
string res;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (st.empty()) {
st.push(pair<char, int>(s[i], 1));
}
else {
auto top = st.top(); st.pop();
if (top.first == s[i]) {
top.second = (top.second + 1) % k;
if (top.second > 0) {
st.push(top);
}
}
else {
st.push(top);
st.push(pair<char, int>(s[i], 1));
}
}
}
while (!st.empty()) {
auto top = st.top(); st.pop();
for (int i = 0; i < top.second; ++i) {
res.push_back(top.first);
}
}
reverse(res.begin(), res.end());
return res;
}
};
austin님의 댓글
- 익명
- 작성일
Runtime: 13 ms, faster than 96.55% of C++ online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: 10.3 MB, less than 63.87% of C++ online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: 10.3 MB, less than 63.87% of C++ online submissions for Remove All Adjacent Duplicates in String II.
class Solution {
public:
string removeDuplicates(string s, int k) {
char prev = 0U;
int cnt = 0;
string ret;
stack<pair<char, int>> t;
for(auto c: s) {
ret.push_back(c);
if (c != prev) {
t.emplace(prev, cnt);
prev = c, cnt = 1;
} else if (++cnt == k) {
ret.resize(ret.size()-k);
tie(prev, cnt) = t.top(); t.pop();
}
}
return ret;
}
};