优化"k"个连续相等字符标识的提示

Question

我正试图解决一个问题：

操作包括选择连续相等的k个字符并将其删除。此操作将尽可能长时间地执行。执行完所有操作后，返回最后一个单词。例如，对于abbcccb和k＝3，输出应该是a。

我可以想出的代码如下：

#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
string helper(string& s, int k) {
if(s.size()<k) return s;

string str;
for(int i=0; i<s.size(); i++){
char currChar=s[i];
int j=i+1, count=0;
while(j<s.size() && count<=k && s[j]==currChar) {
j++;
count++;
}
if(j-i==k) {
for(int k=0; k<i; k++) str.push_back(s[k]);
for(int k=j; k<s.size(); k++) str.push_back(s[k]);
break;
}
}

if(str.empty()) return s;
return helper(str, k);
}
int main() {
// string s="abbcccb";
// string s="abcdef";
// string s="baac";
string s="aba";
cout<<helper(s, 2);
return 0;
}

此处为工作代码。

然而，我认为有一种可能的方法可以进一步优化代码，特别是在我确定k连续字符是否相等的部分。

有人能提供一些建议/想法/解决方案吗？

谢谢。

Answer 1

这是一个标准问题，可以在O(n(时间内使用堆栈解决。这个网站已经给出了完整的解释。请参阅此通过删除K个连续的相同字符来减少字符串