题解 | #小O的字符串重排#

题目链接

题目描述

给定一个只包含小写字母的源字符串 $S$ ，以及两个目标字符串 $T_1$ 和 $T_2$ （均首字母大写，其余小写）。你可以对 $S$ 进行任意重排，并可以改变其中任意字符的大小写。目标是构造一个新字符串 $S'$ ，使其包含尽可能多的非重叠子串 $T_1$ 或 $T_2$ 。求 $T_1$ 和 $T_2$ 出现总次数的最大值。

解题思路

1. 问题转化：资源分配

这个问题的核心是一个资源分配问题。我们拥有的资源是源字符串 $S$ 中的所有字符。由于大小写可以任意转换，所以我们只关心每种字母（'a' 到 'z'）的数量。例如，如果 $S$ 是 "aabbc"，我们的资源就是 {a:2, b:2, c:1}。

我们的目标是使用这些资源来“生产”两种产品：字符串 $T_1$ 和 $T_2$ 。我们想最大化生产出的产品总数。

假设我们决定生产 $k_1$ 个 $T_1$ 和 $k_2$ 个 $T_2$ 。这需要消耗的每种字符 c 的数量为： k_1 * (c 在 T_1 中的数量) + k_2 * (c 在 T_2 中的数量)

这个消耗量不能超过我们在 $S$ 中拥有的该字符的数量。我们的任务就是找到一组非负整数 $(k_1, k_2)$ ，在满足资源限制的前提下，最大化它们的和 $k_1 + k_2$ 。

2. 算法设计：枚举一种产品的数量

这是一个可以通过枚举解决的问题。我们可以枚举其中一种产品（比如 $T_1$ ）的所有可能生产数量，然后对于每种情况，计算另一种产品（ $T_2$ ）最多能生产多少。

确定枚举范围: 我们枚举生产 $T_1$ 的数量，设为 k1。k1 的最小值为 0。其最大值是当我们不生产任何 $T_2$ 时，仅用 $S$ 中的字符资源最多能生产的 $T_1$ 数量。
迭代计算:
- 我们让 k1 从 0 开始，一直到其最大可能值。
- 对于每一个固定的 k1： a. 首先，我们计算生产 k1 个 $T_1$ 需要消耗多少资源。 b. 检查我们拥有的资源（S 中的字符）是否足够。如果不够，那么更大的 k1 值也肯定不够，可以直接结束枚举。 c. 如果资源充足，我们计算出生产后每种字符的剩余数量。 d. 利用这些剩余的字符，我们再贪心地计算最多能生产多少个 $T_2$ 。这个数量就是 k2。 e. 当前方案的总产品数为 k1 + k2。我们用这个值来更新全局的最大值。
最终结果: 遍历完所有可能的 k1 值后，记录下的全局最大值就是最终答案。

算法流程:

预处理: 分别统计 $S$ , $T_1$ , $T_2$ 中每个小写字母的出现频率，存入频率数组 freqS, freqT1, freqT2。
枚举 k1: 循环变量 k1 从 0 开始递增。
检查并计算: 在循环中，对于每个 k1，检查 freqS 是否足以支持 k1 个 T1 的消耗。如果可以，则计算出剩余字符，并根据剩余字符计算出最大可能的 k2。更新最大答案 max(ans, k1 + k2)。
输出: 输出最终答案。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// Function to calculate frequency of characters (case-insensitive)
vector<int> get_freq(const string& s) {
    vector<int> freq(26, 0);
    for (char ch : s) {
        freq[tolower(ch) - 'a']++;
    }
    return freq;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s, t1, t2;
    cin >> s >> t1 >> t2;

    vector<int> freq_s = get_freq(s);
    vector<int> freq_t1 = get_freq(t1);
    vector<int> freq_t2 = get_freq(t2);

    int max_ans = 0;

    for (int k1 = 0; k1 <= s.length() / t1.length() + 1; ++k1) {
        vector<int> remaining_s = freq_s;
        bool possible_k1 = true;

        // Subtract resources for k1 copies of t1
        for (int i = 0; i < 26; ++i) {
            if (remaining_s[i] < (long long)k1 * freq_t1[i]) {
                possible_k1 = false;
                break;
            }
            remaining_s[i] -= k1 * freq_t1[i];
        }

        if (!possible_k1) {
            break; // Cannot make k1 copies, so cannot make k1+1 either
        }

        // With remaining resources, calculate max k2
        int k2 = 2e9; // A large enough number
        bool possible_t2 = false;
        for(int i = 0; i < 26; ++i) {
            if (freq_t2[i] > 0) {
                k2 = min(k2, remaining_s[i] / freq_t2[i]);
                possible_t2 = true;
            }
        }
        
        if (!possible_t2) { // T2 is an empty string, can form infinite
             k2 = 0; // Or handle as per problem spec, assume length > 0
        }
        if (k2 == 2e9) k2 = 0; // T2 had no characters with freq > 0


        max_ans = max(max_ans, k1 + k2);
    }

    cout << max_ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] getFreq(String s) {
        int[] freq = new int[26];
        for (char ch : s.toCharArray()) {
            freq[Character.toLowerCase(ch) - 'a']++;
        }
        return freq;
    }

    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[] freqS = getFreq(s);
        int[] freqT1 = getFreq(t1);
        int[] freqT2 = getFreq(t2);

        int maxAns = 0;

        for (int k1 = 0; ; k1++) {
            int[] remainingS = new int[26];
            System.arraycopy(freqS, 0, remainingS, 0, 26);
            boolean possibleK1 = true;

            for (int i = 0; i < 26; i++) {
                if (remainingS[i] < (long)k1 * freqT1[i]) {
                    possibleK1 = false;
                    break;
                }
                remainingS[i] -= k1 * freqT1[i];
            }

            if (!possibleK1) {
                break;
            }

            int k2 = Integer.MAX_VALUE;
            boolean hasCharsT2 = false;
            for (int i = 0; i < 26; i++) {
                if (freqT2[i] > 0) {
                    hasCharsT2 = true;
                    k2 = Math.min(k2, remainingS[i] / freqT2[i]);
                }
            }

            if (!hasCharsT2) {
                k2 = 0;
            }

            maxAns = Math.max(maxAns, k1 + k2);
        }

        System.out.println(maxAns);
    }
}

import sys
from collections import Counter

def get_freq(s):
    return Counter(s.lower())

def solve():
    s = sys.stdin.readline().strip()
    t1 = sys.stdin.readline().strip()
    t2 = sys.stdin.readline().strip()

    freq_s = get_freq(s)
    freq_t1 = get_freq(t1)
    freq_t2 = get_freq(t2)

    max_ans = 0
    k1 = 0
    while True:
        remaining_s = freq_s.copy()
        possible_k1 = True
        
        # Check if k1 copies of t1 are possible
        for char, count in freq_t1.items():
            if remaining_s[char] < k1 * count:
                possible_k1 = False
                break
            remaining_s[char] -= k1 * count
        
        if not possible_k1:
            break

        # Calculate max k2 with remaining characters
        k2 = float('inf')
        if not freq_t2: # T2 is empty
            k2 = 0
        else:
            for char, count in freq_t2.items():
                k2 = min(k2, remaining_s.get(char, 0) // count)
        
        max_ans = max(max_ans, k1 + int(k2))
        k1 += 1
        
    print(max_ans)

solve()

算法及复杂度

算法: 枚举、贪心
时间复杂度:
- 统计所有字符串的字符频率： $\mathcal{O}(|S| + |T_1| + |T_2|)$ 。
- 主循环枚举 k1 的数量。k1 的最大值不会超过 $|S|$ 。在循环内部，所有操作都只涉及对 26 个字母的常数次计算。
- 因此，总时间复杂度为 $\mathcal{O}(|S|)$ 。
空间复杂度:
- 需要存储三个频率数组/哈希表，其大小固定为 26。
- 因此，空间复杂度为 $\mathcal{O}(1)$ (若不计输入字符串本身)。