c++ - 什么是针对 C++ 中的大小写的字符串的许多子字符串的有效方法？

Question

我正在处理 Hackerrank 上的一些问题，我需要在删除 1 或 0 个元素后确定字符串是否与模式匹配。如果在删除 1 或 0 个元素后，字符串中的每个字符都具有相同的频率，那么我想打印“YES”。否则我打印“NO”。输入是 1 到 10^5 个字符之间的字符串。我所拥有的适用于琐碎的案例，但在某些测试用例上会超时。我应该达到一些返回值，但我认为测试用例只是非常大的输入，我的代码效率太低了。特别是在我使用删除的地方，我将字符串复制 n^2 次，其中 n 是字符串的长度。我可以就地处理字符串，只是跳过每个元素吗？

#include <iostream>
#include <string>
using namespace std;


long countFreq(char someChar,string someStr){
    long count = 0;
    for(int i=0;i<someStr.size();i++){
        if(someStr[i] == someChar)count += 1;
        }
    return count;}

bool allSameFreq(string someStr){
    long freq = countFreq(someStr[0],someStr);
    for(char someChr:someStr){
        if(countFreq(someChr,someStr)!=freq)return false;
        }
    return true;}


int main(){
    string pattern;
    cin>>pattern;

    if(allSameFreq(pattern)==true){cout<<"YES";return 0;}
    else {
        for(int i=0;i<pattern.size();i++){
            string copy = pattern;
            copy.erase(i,1);
            if(allSameFreq(copy)==true){cout<<"YES";return 0;}
            }
        cout<<"NO";
        }
    return 0;
}

编辑:有人指出，这可以通过另一种占用内存较少的方式解决。不过，我对最初的问题很好奇:什么是一种有效的方法来迭代字符串(或其他)并根据条件测试“字符串减去每个值”而不每次都复制字符串？

Answer 1

我发现了一种无需复制即可高效操作子列表的方法。您必须能够访问指向字符串元素的指针，将字符串视为链表。因此，根据您想要更改字符串的方式，您移动一个或几个指针，保存您修改的指针的值。