小O的字符串重排

[题目链接](https://www.nowcoder.com/practice/729b24646e17478db41e4ad2675e9d7e)

思路

给定字符串 （全小写），以及两个模式串 （首字母大写，其余小写）。可以任意重排 并改变大小写，求新串中最多能包含多少个不重叠的 或 子串。

关键观察

由于可以任意重排和任意改变大小写，我们可以自由地把字符放到任何位置并赋予任何大小写。因此问题本质上和位置、大小写无关，只和字母频次有关。

将所有字符统一为小写来计数：

• 统计 中各字母出现次数 ；
• 统计 中各字母出现次数 （忽略大小写）；
• 统计 中各字母出现次数 （忽略大小写）。

枚举求解

设使用 个 和 个 ，则对每个字母 ，需满足 。

目标是最大化 。

枚举 从 到 （），扣除 个 所需字母后，贪心计算剩余字母最多能拼出多少个 ：

$$

答案为所有 对应的 的最大值。

复杂度

，每次枚举内遍历 26 个字母，总时间 ，满足约束。

代码

C++

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

int main() {
    string s, t1, t2;
    cin >> s >> t1 >> t2;

    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;

    vector<int> need1(26, 0), need2(26, 0);
    for (char c : t1) need1[tolower(c) - 'a']++;
    for (char c : t2) need2[tolower(c) - 'a']++;

    int maxT1 = INT_MAX;
    for (int i = 0; i < 26; i++) {
        if (need1[i] > 0) {
            maxT1 = min(maxT1, cnt[i] / need1[i]);
        }
    }
    if (maxT1 == INT_MAX) maxT1 = (int)s.size();

    int ans = 0;
    for (int x = 0; x <= maxT1; x++) {
        int y = INT_MAX;
        bool hasNeed2 = false;
        for (int i = 0; i < 26; i++) {
            int rem = cnt[i] - x * need1[i];
            if (need2[i] > 0) {
                hasNeed2 = true;
                y = min(y, rem / need2[i]);
            }
        }
        if (!hasNeed2) y = 0;
        ans = max(ans, x + y);
    }

    cout << ans << endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t1 = sc.next();
        String t2 = sc.next();

        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;

        int[] need1 = new int[26], need2 = new int[26];
        for (char c : t1.toCharArray()) need1[Character.toLowerCase(c) - 'a']++;
        for (char c : t2.toCharArray()) need2[Character.toLowerCase(c) - 'a']++;

        int maxT1 = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            if (need1[i] > 0) {
                maxT1 = Math.min(maxT1, cnt[i] / need1[i]);
            }
        }
        if (maxT1 == Integer.MAX_VALUE) maxT1 = s.length();

        int ans = 0;
        for (int x = 0; x <= maxT1; x++) {
            int y = Integer.MAX_VALUE;
            boolean hasNeed2 = false;
            for (int i = 0; i < 26; i++) {
                int rem = cnt[i] - x * need1[i];
                if (need2[i] > 0) {
                    hasNeed2 = true;
                    y = Math.min(y, rem / need2[i]);
                }
            }
            if (!hasNeed2) y = 0;
            ans = Math.max(ans, x + y);
        }

        System.out.println(ans);
    }
}