c++ - 最常见的字母子串

Question

我的逻辑适用于较小的输入，我如何才能更好地接受较大的输入。

问)
该程序必须接受仅包含小写字母的字符串 S 和 Q 查询作为输入。每个查询包含两个整数，表示 S 中子字符串的起始索引和结束索引。对于每个查询，程序必须打印指定子字符串中最常出现的字母表。如果有两个或多个字母相同的频率，那么程序必须打印按字母顺序排列最少的字母。

边界条件:
2 <= S 的长度 <= 1000
1 <= Q <= 10^5

示例:
输入:坏坏床
4
0 8
1 4
0 5
2 7
输出:
b
一个
一个

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char** argv)
{
  string s;
  cin >> s;
  int k;
  cin >> k;
  int x, y;
  while (k--)
  {
    cin >> x >> y;
    map<char, int>counter;
    string ss = s.substr(x, y - x + 1);
    set <char>sample;
    for (auto i : ss)
      sample.insert(i);
    int maxx = -1, st; char anss;
    for (auto i : sample)
      if ((st = count(ss.begin(), ss.end(), i)) > maxx)
      {
        maxx = st;
        anss = i;
      }
    cout << anss << endl;
  }
}

Answer 1

以下代码会浪费大量内存，但每个查询的查找时间都是O(1):

int main() {
    std::string s;
    int q = 0, start = 0, end = 0;
    std::cin >> s;
    std::cin >> q;

    auto mem = std::make_unique<int[]>(26 * s.length());
    for (int i = 0; i < s.length(); i++) {
        mem[i * 26 + s[i] - 'a']++;
        if (i < (s.length()-1)) {
            for (int l = 0; l < 26; l++) {
                mem[(i+1) * 26 + l] = mem[i * 26 + l];
            }
        }
    }

    for (int i = 0; i < q; i++) {
        std::cin >> start >> end;
        int max_val = 0;
        int max_idx = -1;
        for (int l = 0; l < 26; l++) {
            auto v = (mem[end * 26 + l] - mem[start * 26 + l]);
            if (v > max_val) {
                max_val = v;
                max_idx = l;
            }
        }

        std::cout << (char)('a' + max_idx) << std::endl;
    }

    return 0;
}