c++求解字符个数求解

Question

描述

给定一个字符串，由字母和数字构成。将该字符串从某个点断开，分成两个部分，设这两个部分为 A 和 B，A 和 B 都不为空。有一些字符会同时出现在 A 和 B 中。假设 A 的长度小于等于 B的长度，在 B 中取出和 A 长度相等的连续子串，设为 C，统计该子串和 A 共同出现的字符个数。从不同位置断开，取不同子串，同时出现在 A 和 C 中的字符个数是不一样的。求同时出现在 A 和 C 中的字符个数的最大值。

举例：

字符串："abAabc"

第一个位置为断点，分为两部分：A 为"a"，B 为 "bAabc"。在 B 中取长度为 1 的连续子串，有 "b"、"A"、"a"、"b"、"c"，共同的字符个数分别为 0,0,1,0,0。

第二个位置为端点，分为两部分：A 为"ab"，B 为 "Aabc"。在 B 中取长度为 2 的连续子串，有 "Aa"、"ab"、"bc"，共同的字符个数分别为 1,2,1。

依此类推。字符个数最大值为 2。

输入描述

输入一行字符串，该字符串只包含 'A' - 'Z' 'a'- 'z' '0' - '9'这些字符。

输出描述

输出一行一个整数，表示同时出现在 A 和 B 中的字符最多的个数。

用例输入 1
11111111
用例输出 1
1
用例输入 2
abAabc
用例输出 2
2
用例输入 3

用例输出 3
6
提示

样例1：不管从哪个位置断开，A 和 B 中同时包含的只有 1。

样例2：见题面。

数据范围
对于 100% 的数据，字符串的长度最小为 2， 最大为 100。

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以采用滑动窗口的方法。首先遍历整个字符串，维护两个哈希集合，一个用于存储子串A中的字符，另一个用于存储子串B中的字符。当移动到新的位置时，我们会更新子串A和子串B，并计算它们之间的交集大小。这个过程可以使用C++实现如下：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int max_common_chars(string s) {
    int n = s.length();
    unordered_set<char> set_a, set_b;
    int max_common = 0;

    for (int i = 0; i < n; ++i) {
        // 当前子串A的结束位置
        if (i >= 1) {
            set_a.erase(s[i - 1]);
        }
        // 更新子串A
        set_a.insert(s[i]);

        // 当前子串B的起始位置
        if (i + 1 <= n - 1) {
            set_b.insert(s[i + 1]);
        }

        // 计算子串A和子串B（即C）的交集大小
        int common = 0;
        for (char c : set_a) {
            if (set_b.find(c) != set_b.end()) {
                ++common;
            }
        }
        max_common = max(max_common, common);
    }

    return max_common;
}

int main() {
    string input;
    cout << "请输入字符串: ";
    cin >> input;

    int result = max_common_chars(input);
    cout << "同时出现在 A 和 C 中的字符最多个数为: " << result << endl;

    return 0;
}

这段代码首先定义了一个max_common_chars函数，它接收一个字符串s作为参数。然后我们创建了两个哈希集合set_a和set_b，分别存储子串A和子串B中的字符。接下来，我们遍历字符串s，每次迭代都会更新子串A和子串B，并计算它们的交集大小。在主函数main中，我们读入用户输入的字符串并调用max_common_chars函数得到结果，最后输出结果。

这个程序的时间复杂度是O(n)，其中n是字符串的长度，因为我们只遍历了一次字符串。空间复杂度也是O(n)，因为在最坏的情况下，每个字符都可能存在于子串A或子串B中。