特别恶心的一道题
首先基础做法是单调栈,如果没有至少repetition个letter的限制,直接从左往右遍历,维护一个递增栈即可
加上这个限制之后,会有两个改动:
- 判断是否当前出栈元素是letter,删除后会导致后面的letter不够凑到repetition,这里需要把原栈的所有元素进行归档(代码31行)
- 处理一直是递增字符串的特殊case
代码如下
class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
string result;
int n = s.length();
stack<char> st;
int letter_count = 0;
int need_delete = n - k;
// int last_repetition = 0;
vector<int> pre(n + 5, 0);
for(int i = 0; i < n; ++i) {
if (i == 0) pre[i] = s[i] == letter;
else pre[i] = pre[i - 1] + (s[i] == letter);
}
int end_flag = n;
for(int i = 0; i < n; ++i) {
int still_have = pre[n - 1] - pre[i] + (s[i] == letter);
// printf("%d\n", still_have);
while(!st.empty()) {
char tt = st.top();
if (need_delete == 0) break;
if (tt == letter && letter_count - 1 + still_have < repetition) {
string tmp;
while(!st.empty()) {
tmp += st.top();
st.pop();
}
reverse(tmp.begin(), tmp.end());
result += tmp;
// printf("%s\n", result.c_str());
break;
}
if(tt > s[i]) {
st.pop();
need_delete --;
if(tt == letter) letter_count --;
// printf("pop %c %d %d\n", tt, need_delete, letter_count);
} else {
break;
}
}
st.push(s[i]);
if(s[i] == letter) letter_count ++;
// printf("push %c %d %d\n", s[i], need_delete, letter_count);
}
string tmp;
while(!st.empty()) {
tmp += st.top();
st.pop();
}
reverse(tmp.begin(), tmp.end());
result += tmp;
// printf("%s\n", result.c_str());
result = result.substr(0, k);
// for special case
int cnt = 0;
for(int i = 0; i < k; ++i) {
if(result[i] == letter) {
cnt ++;
}
}
for(int i = k - 1; i >= 0; --i) {
if(result[i] != letter && cnt < repetition) {
result[i] = letter;
cnt ++;
}
}
return result;
}
};