csp信奥赛C++高频考点专项训练之字符串 --【字符统计】：「MYOI-R3」字符串

csp信奥赛C++高频考点专项训练之字符串 --【字符统计】：「MYOI-R3」字符串

题目描述

给定字符串s , t s,ts,t。

现在你要在s , t s,ts,t中删除一些字符并将它们重新排列使s = t s=ts=t。

问操作后的∣ s ∣ |s|∣s∣（即字符串s ss的长度）最大是多少？

输入格式

第一行一个字符串s ss。

第二行一个字符串t tt。

输出格式

一行一个整数，表示操作后的∣ s ∣ |s|∣s∣的最大值。

输入输出样例 1

输入 1

abc bc

输出 1

2

输入输出样例 2

输入 2

aaaaa bbbbb

输出 2

0

说明/提示

在第一个样例中，将a删除，留下bc。

此时∣ s ∣ = 2 |s|=2∣s∣=2，可以证明这是最优解。

在第二个样例中，将aaaaa删除，留下空串。
将bbbbb删除，留下空串。

此时∣ s ∣ = 0 |s|=0∣s∣=0，可以证明这是最优解。

本题采用捆绑测试。

记n = max ⁡ ( ∣ s ∣ , ∣ t ∣ ) n=\max(|s|,|t|)n=max(∣s∣,∣t∣)。

对于100 % 100\%100%的数据，1 ≤ ∣ s ∣ , ∣ t ∣ ≤ 10 5 1 \le |s|,|t| \le 10^51≤∣s∣,∣t∣≤105，字符串均由小写字母组成。

特殊性质A \text{A}A：s ss是一个a ∼ z \text{a}\sim\text{z}a∼z的排列。

特殊性质B \text{B}B：保证s i , t i ∈ { a , b } s_i,t_i\in\{\text{a},\text{b} \}si​,ti​∈{a,b}。

思路分析

题目要求：删除两个字符串中的部分字符，并重新排列剩下的字符，使得两个字符串相等。由于可以任意重排，最终字符串的字符组成只取决于两个字符串中字符出现的频数。对于每个字符，能保留的最大数量就是两个字符串中该字符出现次数的最小值。因此，答案等于所有字符的min(cnt_s[ch], cnt_t[ch])之和。

实现步骤：

1. 读入字符串s和t。
2. 用两个长度为 26 的数组a和b分别统计s和t中每个字母出现的次数。
3. 遍历 26 个字母，累加min(a[i], b[i])到答案。
4. 输出答案。

时间复杂度 O(|s|+|t|)，空间 O(1)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;string s,t;//两个输入字符串inta[26];//桶a：统计s中每个字母出现次数intb[26];//桶b：统计t中每个字母出现次数intans=0;//最终能得到的字符串长度intmain(){cin>>s>>t;//读入字符串//统计s中每个字母的出现次数for(inti=0;i<s.size();i++){a[s[i]-'a']++;//将字符转换为0~25的下标并累加}//统计t中每个字母的出现次数for(inti=0;i<t.size();i++){b[t[i]-'a']++;}//累加每个字母的最小出现次数for(inti=0;i<26;i++){ans+=min(a[i],b[i]);//取较小值并累加}cout<<ans;//输出结果return0;}

功能分析

• 输入处理：从标准输入读取两个字符串s和t。
• 频数统计：使用两个整型数组a和b分别记录s和t中每个小写字母（'a'~'z'）出现的次数。通过字符 - 'a'将字符映射到数组下标。
• 答案计算：遍历 26 个字母，将两个数组对应位置的最小值累加到ans。
• 输出结果：打印ans，即操作后字符串的最大可能长度。

该算法正确解决了问题，时间复杂度 O(|s|+|t|)，空间复杂度 O(1)，满足题目数据范围（|s|,|t| ≤ 10^5），可通过所有测试点。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}