题解 | 小O的字符串重排

#include <bits/stdc++.h>
using namespace std;

array<long long, 26> countNeed(const string& p) {
    array<long long, 26> need{};
    need.fill(0);
    for (char ch : p) {
        char c = tolower((unsigned char)ch);
        need[c - 'a']++;
    }
    return need;
}
int main() {
    string s, a, b;
    cin >> s >> a >> b;
    // 库存
    array<long long, 26> cnt{};
    cnt.fill(0);
    for (char ch : s) cnt[ch - 'a']++;

    auto needA = countNeed(a);
    auto needB = countNeed(b);

    // 计算最多能做多少份 a（作为枚举上界）
    auto maxCopies = [&](const array<long long, 26>& need)->long long{
        long long lim = (long long)1e18;
        for (int c = 0; c < 26; c++) {
            if (need[c]) lim = min(lim, cnt[c] / need[c]);
        }
        if (lim == (long long)1e18) return 0; // 模式长度>=1，正常不会到这
        return lim;
    };
    long long maxA = maxCopies(needA);

    long long best = 0;
    for (long long x = 0; x <= maxA; ++x) {
        // 剩余库存
        array<long long, 26> left = cnt;
        bool ok = true;
        for (int c = 0; c < 26; c++) {
            left[c] -= x * needA[c];
            if (left[c] < 0) {
                ok = false;
                break;
            }
        }
        if (!ok) break; // x 再增大只会更差

        // 尽量做 b
        long long y = (long long)1e18;
        bool anyB = false;
        for (int c = 0; c < 26; c++) {
            if (needB[c]) {
                anyB = true;
                y = min(y, left[c] / needB[c]);
            }
        }
        if (!anyB) y = 0; // b 长度至少为1，通常不会发生

        best = max(best, x + y);
    }
    cout << best << '\n';
    return 0;
}