序号问题常用模板/思路蓝桥杯真题 (链接)1统计不同字符个数使用set集合存储字符返回len(set)即可不同子串 (2019 省赛)子串分值 (2020 省赛)2判断是否有重复字符利用set去重后比较长度或用collections.Counter统计频次重复字符串 (2020 国赛)重复的串 (2024 国赛)3找出第一个只出现一次的字符1. 用哈希表 (Counter) 统计频率2. 再次遍历字符串找到第一个频率为1的字符字串分值 (2020 省赛)找第一个只出现一次的字符4统计每个字符出现次数使用collections.Counter直接生成频数字典重复字符串 (2020 国赛)子串分值和 (2020 省赛)5字符串去重使用set进行去重会丢失顺序或遍历字符串维护一个seen集合和一个结果列表子串去重 (2025 国赛)串中取3个不重复字母6判断两个字符串字母相同对两个字符串的字符进行排序 (sorted) 后比较是否相等字符串对比 (基础练习)7最长无重复字符子串滑动窗口维护窗口用集合/数组记录字符是否出现过右指针扩展遇重复则移动左指针最长不重复子串 (省赛训练题)此题为LeetCode经典题的蓝桥版8拆分字符串使两部分不同字符之和最大根据题目不同常用前缀和思想预计算每个分割点前后的不同字符数或暴力枚举分割点切开字符串 (2015 国赛)分割字符串 (2024 国赛一个字符串的非空子串是指字符串中长度至少为1的连续的一段字符组成的串。例如字符串有非空子串,,,,,,一共7个。注意在计算时只算本质不同的串的个数。请问字符串0100110001010001有多少个不同的非空子串#include bits/stdc.h using namespace std; int main() { // 请在此输入您的代码 setstring a; string s0100110001010001; for(int len1;lens.size();len){ for(int i0;is.size()-len;i){ a.insert(s.substr(i,len)); } } couta.size(); return 0; }子串分值和题目描述对于一个字符串我们定义的分值()为中出现的不同的字符个数。例如(“”)2(“”)3,(“”)1。现在给定一个字符串[0...−1]长度为请你计算对于所有的非空子串[...](0≤≤)([...])的和是多少。输入描述输入一行包含一个由小写字母组成的字符串。其中1≤≤105。输出描述输出一个整数表示答案。输入输出样例示例 1输入ababc输出28只能过60%样例代码#include bits/stdc.h using namespace std; int main() { string s; cin s; int n s.size(); long long ans 0; for (int i 0; i n; i) { unordered_setchar seen; // 或者 setchar for (int j i; j n; j) { seen.insert(s[j]); ans seen.size(); } } cout ans endl; return 0; }定义 dp[i] 表示以第 i 个字符结尾的所有子串的分值之和。转移dp[i] dp[i-1] (i - last[s[i]])其中 last[c] 是字符 c 上一次出现的位置初始为 -1。最后答案 sum(dp[i])。#include bits/stdc.h using namespace std; int main() { string s; cin s; int n s.size(); vectorint last(26, -1); long long ans 0, dp 0; for (int i 0; i n; i) { int c s[i] - a; dp i - last[c]; ans dp; last[c] i; } cout ans endl; return 0; }三、重复字符串题目描述如果一个字符串恰好可以由某个字符串重复次得到我们就称是次重复字符串。例如 abcabcabc可以看作是 abc 重复3次得到所以 abcabcabc 是3次重复字符串。同理 aaaaaa 既是2次重复字符串、又是3次重复字符串和6次重复字符串。现在给定一个字符串请你计算最少要修改其中几个字符可以使变为一个次字符串输入描述输入第一行包含一个整数。第二行包含一个只含小写字母的字符串。其中1≤≤105,1≤∣∣≤105。其中∣∣表示的 长度。输出描述输出一个整数代表答案。如果无法修改成次重复字符串输出−1。输入输出样例示例 1输入2aabbaa输出2对于这个问题如果字符串长度 n 不是 K 的倍数直接输出 -1。否则令 m n / K将字符串分成 K 段每段长度为 m。要使所有段完全相同对于每个偏移位置 i0 ≤ i m需要将第 0 段、第 1 段、……、第 K-1 段的第 i 个字符改成相同字符。统计这 K 个字符中出现次数最多的字符保留它其余 K - max_cnt 个字符需要修改。对所有 i 求和即得最少修改次数。#include bits/stdc.h using namespace std; int main() { int K; string S; cin K S; int n S.size(); if (n % K ! 0) { cout -1 endl; return 0; } int m n / K; int ans 0; for (int i 0; i m; i) { int cnt[26] {0}; for (int j 0; j K; j) { char c S[j * m i]; cnt[c - a]; } int maxcnt *max_element(cnt, cnt 26); ans K - maxcnt; } cout ans endl; return 0; }