problem
solution
- TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46class Solution {
public:
bool isValid(string s, int i, int k){
if(i+k-1>=s.size()) return false;
for(int j=i;j<i+k;++j){
if(s[j]!=s[i]) return false;
}
return true;
}
bool islegal(stack<char> s, char c, int k){
if(s.size()<k-1) return false;
stack<char> temp = s;
while(!temp.empty() && temp.top() == c){
temp.pop();
k--;
}
return k==1;
}
string removeDuplicates(string s, int k) {
stack<char> sta;
int n = s.size();
for(int i=0;i<n;){
if(isValid(s,i,k)){
i+=k;
}
else{
if(islegal(sta, s[i], k)){
while(!sta.empty() && sta.top() == s[i]){
sta.pop();
}
}
else sta.push(s[i]);
i++;
}
}
string ret;
while(!sta.empty()){
ret+=sta.top();
sta.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};option 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
string removeDuplicates(string s, int k) {
stack<pair<char,int>> sta;
int n = s.size();
for(char c:s){
if(!sta.empty() && sta.top().first == c){
auto p = sta.top();
sta.pop();
if(p.second == k-1) continue;
else sta.push(make_pair(c,p.second+1));
}
else sta.push(make_pair(c,1));
}
string ret;
while(!sta.empty()){
ret.append(sta.top().second, sta.top().first);
sta.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};analysis
- time complexity
O(n) - space complexity
O(n)