AtCoder题解｜ABC 98B Cut and Count

题目信息 📚

【题目描述】

You are given a string $S$ of length $N$ consisting of lowercase English letters. We will cut this string at one position into two strings $X$ and $Y$. Here, we would like to maximize the number of different letters contained in both $X$ and $Y$. Find the largest possible number of different letters contained in both $X$ and $Y$ when we cut the string at the optimal position.

【输入】

The input is given from Standard Input in the following format:

$N$

$S$

【输出】

Print the largest possible number of different letters contained in both $X$ and $Y$.

【数据范围】

$2 \leq N \leq 100$
$|S| = N$
$S$ consists of lowercase English letters.

【输入样例1】

6
aabbca

【输出样例1】

If we cut the string between the third and fourth letters into $X = \text{aab}$ and $Y = \text{bca}$, the letters contained in both $X$ and $Y$ are $a$ and $b$. There will never be three or more different letters contained in both $X$ and $Y$, so the answer is $2$.

【输入样例2】

10
aaaaaaaaaa

【输出样例2】

However we divide $S$, only $a$ will be contained in both $X$ and $Y$.

【输入样例3】

45
tgxgdqkyjzhyputjjtllptdfxocrylqfqjynmfbfucbir

【输出样例3】

【题目来源】

https://atcoder.jp/contests/abc098/tasks/abc098_b

题目解析 🍉

【题目分析】

枚举所有可能的划分方式，再编写函数统计两个字符串共同元素的数量。

统计方式：

将两个字符串转化成去重的 set1 和 set2
对 set1 和 set2 取交集，得到 set3
set3 的元素个数即为所求数量

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

// 统计字符串s1和s2的共同字符数
int compare(string s1, string s2) {
    set<char> st1, st2;
    for (int i = 0; i < s1.size(); i++) st1.insert(s1[i]);
    for (int i = 0; i < s2.size(); i++) st2.insert(s2[i]);

    int cnt = 0;
    for (auto t: st1) {
        if (st2.find(t) != st2.end()) cnt++;
    }
    return cnt;
}

int main() {
    int n;
    string s;
    cin >> n >> s;
  
    // 枚举所有可能，取最大值
    int ans = -1;
    for (int i = 0; i < s.size() - 1; i++) {
        string s1 = s.substr(0, i + 1);
        string s2 = s.substr(i + 1);
        ans = max(ans, compare(s1, s2));
    }
    cout << ans << endl;

    return 0;
}

【Python代码】

# 统计字符串s1和s2的共同字符数
def f(s1, s2):
    set1 = set(s1)
    set2 = set(s2)
    cnt = 0
    for ch in set2:
        if ch in set1:
            cnt += 1
    return cnt


def main():
    # 读入字符串
    n = int(input())
    s = input()

    # 枚举所有可能，取最大值
    res = 0
    for i in range(1, n):
        s1 = s[0:i]
        s2 = s[i:n]
        res = max(res, f(s1, s2))
    print(res)


if __name__ == "__main__":
    main()

利用Python set 自带操作の优化版

# 统计字符串s1和s2的共同字符数
def f(s1, s2):
    return len(set(s1) & set(s2)) # 利用set的取交集操作进行优化

def main():
    # 读入字符串
    n = int(input())
    s = input()

    # 枚举所有可能，取最大值
    res = 0
    for i in range(1, n):
        s1 = s[0:i]
        s2 = s[i:n]
        res = max(res, f(s1, s2))
    print(res)


if __name__ == "__main__":
    main()