A29391. 最多删除两个字符
填空题
较难
知识点
题目描述
最多删除两个字符
题目描述
给定一个仅由小写英文字母组成的字符串，最多删两个字符后，能得到多少种不同的字符串？
时间限制：5000 内存限制：65536
输入
输入在一行中给出长度在区间 [3, 106] 内的仅由小写英文字母组成的字符串。
输出
在一行中输出最多删两个字符后所能得到的不同字符串的个数。
样例输入
ababcc样例输出
15提示
样例解释：
1、删除 0 个字符后得到 `ababcc`；
2、删除 1 个字符后得到 `babcc`, `aabcc`, `abbcc`, `abacc`, `ababc`；
3、删除 2 个字符后得到 `abcc`, `bbcc`, `bacc`, `babc`, `aacc`, `aabc`, `abbc`, `abac`, `abab`。
参考答案
#include <iostream>
#include <string>
#include <set>
// 函数用于计算最多删除两个字符后能得到的不同字符串的数量
int countDistinctStrings(const std::string& s) {
std::set<std::string> distinctStrings;
int n = s.length();
// 不删除字符的情况
distinctStrings.insert(s);
// 删除一个字符的情况
for (int i = 0; i < n; ++i) {
std::string newStr = s.substr(0, i) + s.substr(i + 1);
distinctStrings.insert(newStr);
}
// 删除两个字符的情况
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
std::string newStr = s.substr(0, i) + s.substr(i + 1, j - i - 1) + s.substr(j + 1);
distinctStrings.insert(newStr);
}
}
return distinctStrings.size();
}
int main() {
std::string s;
std::cin >> s;
std::cout << countDistinctStrings(s) << std::endl;
return 0;
}
上一题
下一题