首页 > 试题广场 >

小O的字符串重排

[编程题]小O的字符串重排
  • 热度指数：177 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小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。
算法知识视频讲解
添加回答
Python
理智的亚瑟才华横溢头像 理智的亚瑟才华横溢
import sys
from collections import Counter

def singleArrange(longstr:Counter[str],a:str) -> int:
    Num = 0
    StopAll = True
    sub = Counter(a)
    for idx1 in sub.keys():
        if idx1 not in longstr:
            return Num
   
    while 1:
        for idx1 in sub.keys():
            if sub[idx1]>longstr[idx1]:
                StopAll = False
                break
        if not StopAll:
            break
        for idx1 in a:
            sub[idx1] += 1
        Num +=1
    return Num

def countArrange(a:List[str]) -> int:
    a[1] = a[1].lower()
    a[2] = a[2].lower()
    longstr = Counter(a[0])
    Num1 = singleArrange(longstr,a[1])
    if Num1>0:
        for idx1 in a[1]:
            longstr[idx1] -= Num1
    Num2 = singleArrange(longstr,a[2])
    return Num1+Num2

a = []
for line in sys.stdin:
    a.append(line.split('\n')[0])
print(countArrange(a))
发表于 2026-04-22 04:44:05 回复(0)
Sen🍓🍀头像 Sen🍓🍀
字符串 a 可能为 b 前缀 (?
发表于 2025-10-27 17:20:08 回复(0)
提交观点

问题信息

贪心 字符串 OPPO
难度：
2条回答 1800浏览

热门推荐

相关试题

小O的字符串重排

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号