小O的字符串重排

OPPO 笔试真题 · 2024 秋招 · AI/算法岗

判题请到牛客原题提交。

题目描述

小O有一个字符串 $s$ ，她希望重新排列这个字符串，并改变字符的大小写，使得新的字符串包含尽可能多的字符串 $a$ 或者字符串 $b$。请问小O最多能包含多少个子串 $a$ 和子串 $b$ 。

如果字符串 $t$ 可以通过从字符串 $s$ 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则字符串 $t$ 是字符串 $s$ 的子串。

输入格式

第一行输入一个字符串 $s$ ，仅包含小写字母。

第二行输入一个字符串 $a$ ，首字母大写，其余小写。

第三行输入一个字符串 $b$ ，首字母大写，其余小写。

除此之外，保证 $1 \leq |s|, |a|, |b| \leq 10^5$ ，即保证每个字符串至多由 $10^5$ 个字符构成。

输出格式

在一行上输出一个正整数，表示最多能包含多少个子串 $a$ 和子串 $b$ 。

示例

示例 1

输入：

abcdefg
Abc
Fge

输出：

2

说明：

将字符串修改成 AbcdFge，包含两个子串 Abc 和 Fge。

---

解题思路

第一步：理解问题本质

字符串可以任意重排、也可以任意改大小写，这两条自由度合起来意味着：
原串里字符的排列顺序完全不重要，唯一的硬约束只剩下一条 ——

每种字母用掉的个数，不能超过 s 里该字母的个数。

大小写只是「外观」：模式串 a 的首字母要求大写、其余小写，但用掉的仍然是同一个字母本身
（输出里的大写 C 和小写 c 消耗的都是 s 里的一个 c）。所以记账时统一按小写字母数。

第二步：一个子串 = 一份字符清单

一个子串 a 消耗的清单就是 a 的全部字母，b 同理。既然顺序完全自由，
就把每个子串摆成字符串里互不重叠的一段 —— 摆在哪、谁在前，都不影响可行性，
只影响「一共用掉多少字符」。于是问题变成一句很朴素的话：

用 s 里的字母，最多能拼出几段 a 加几段 b。

第三步：暴力解法（为什么不能用）

要同时决定「a 拼几份」和「b 拼几份」。直接枚举两个份数是 O(n^2)，
而枚举所有排列再枚举所有大小写更是阶乘级。必须找一个只需要枚举一个维度的做法。

第四步：固定 a 的份数，剩下的贪心算 b

设 a 拼了 x 份。此时剩余字符能拼出的 b 的份数有一个精确公式：
每种字母都不可替代，份数由「最紧」的那种字母决定：

y = min over c in b  ( 剩余 c 的个数 // b 中 c 的个数 )

只要某个字母不够，y 就受限；只要每种字母都够，y 份一定摆得下（互不重叠、
顺序随意）。固定 x 时，y 当然是越大越好 —— 目标就是 x + y 最大。

于是只枚举 x（从 0 到「s 最多能拼出几份 a」），每轮算一次 y，取 x + y 的最大值。
x 的上限不超过 |s| / |a|，每轮只扫两个模式串的字母表（至多 26 种），
总复杂度 O(26 * |s| / |a|)，|s| = 10^5 时最坏也只有两百多万次基本运算。

第五步：枚举时的扣减技巧

每轮结束后把「一份 a 的消耗」从剩余计数里扣掉，而不是每轮重新拷贝一份计数器，
这样既省内存也省时间。

---

完整代码实现

import sys
from collections import Counter


def max_copies(remain: Counter, need: Counter) -> int:
    """remain 里最多能装下几份 need（逐字符取最小值）"""
    best = -1
    for ch, c in need.items():
        cur = remain.get(ch, 0) // c
        if best < 0 or cur < best:
            best = cur
    return 0 if best < 0 else best


def solve() -> None:
    """枚举 a 的份数，剩下的字符贪心拼 b"""
    data = sys.stdin.read().split()
    if len(data) < 3:
        return

    s, a, b = data[0], data[1], data[2]

    cnt = Counter(s)
    need_a = Counter(a.lower())   # 只关心字母，大小写可以自由控制
    need_b = Counter(b.lower())

    # a 最多能拼出的份数
    limit = max_copies(cnt, need_a)

    ans = 0
    remain = Counter(cnt)
    for x in range(limit + 1):
        # 当前方案：x 份 a，剩余字符尽量拼 b
        total = x + max_copies(remain, need_b)
        if total > ans:
            ans = total
        # 为下一轮预留：再消耗一份 a
        for ch, c in need_a.items():
            remain[ch] -= c

    sys.stdout.write(str(ans) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

以题面样例 s = "abcdefg"、a = "Abc"、b = "Fge" 为例。

字符账本：a,b,c,d,e,f,g 各 1 个。a 需要 a,b,c（首字母大写），b 需要 f,g,e。

a 的份数 x	剩余字符	还能拼几份 b	x + y
0	a,b,c,d,e,f,g	1（f、g、e 都各有一个）	1
1	d,e,f,g（a、b、c 被用掉）	1（f、g、e 仍在）	2

a 的份数上限是 1（b、c 各只有 1 个），所以枚举到 x = 1 就结束，
答案是 2。构造出来的字符串正是说明里的 AbcdFge：
Abc 段 + d + Fge 段。

再看一组：s = "aa"、a = "A"、b = "A"。x 可以从 0 枚举到 2，
x = 0 时能拼 2 份 b，x = 1 时剩 1 个 a 能拼 1 份 b，x = 2 时剩 0 个，
三种方案的总数都是 2，答案 2 —— 两个字符，一共就这么多位置。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举所有排列 × 所有大小写	O(n! · 2^n)	O(n)	只能验证极小的数据
枚举 a、b 两个份数并检查字符够不够	O((|s|/|a|) · (|s|/|b|) · 26)	O(26)	正确但多了一层不必要的枚举
枚举 a 的份数 + 贪心算 b 的份数	O(26 · |s| / |a|)	O(26)	推荐，最坏约 2×10^6 次运算

---

易错点总结

1. 把大小写当成两种资源

s 里只有小写字母，但输出里需要大写首字母。'A' 与 'a' 消耗的是同一份资源，
记账时要用 Counter(a.lower())，不能按原样区分大小写。

2. 数 b 的份数时漏掉字母

只数首字母会算错，必须对 b 中每种字母都算一次 剩余 // 需要，再取最小值 ——
最紧的那种字母才是瓶颈。少看一种字母，就会算出一份根本拼不出来的方案。

3. 枚举上限没算清楚

x 只能枚举到 s 真正能拼出的份数。多枚举会让剩余计数变成负数，
max_copies 于是退回 0，而 x 还在往上涨 —— 答案会变成一个荒唐的大数。
上限用「逐字母取最小值」算一次即可。

4. 认为答案一定 ≥ 1

b 或 a 里出现 s 中根本没有的字母时，一份也拼不出来，答案是 0。
题面写的是「正整数」但逻辑上允许 0，按实际输出即可。

5. s 里的「多余字符」不用处理

拼不完的字符随便丢在字符串的某个位置，不会破坏已经摆好的子串。
不需要把它们也塞进某个子串里。

---

扩展思考

• 如果只能改大小写、不能重排，问题就变成在原串里找匹配，需要用 KMP 或字符串哈希。
• 如果字符不是从 s 里消耗、而是可以无限供应，那就不存在争用，只比较两个模式串
  「每个字符能换回多少分」即可，答案直接是 |s| / min(|a|, |b|)。
• 模式串多于两个时，「固定一个、贪心其余」的做法不再正确，需要二分答案配合
  可行性判定，或者用搜索 / 整数规划求解。