题解 | #不同字符#

题目链接

不同字符

题目描述

给定一个长度为 $n$ 的字符串，该字符串只包含大小写字母和阿拉伯数字。需要计算字符串中有多少个不同的字符。

解题思路

本题的目标是统计字符串中唯一字符的数量。解决此类问题的最直接方法是使用集合（Set）数据结构，因为集合本身就具有元素唯一性的特点。

具体思路如下：

创建一个空的集合，用于存储出现过的字符。
遍历输入的字符串 $s$ 。
对于字符串中的每一个字符，我们尝试将其加入集合中。如果该字符已经存在于集合中，集合不会发生变化；如果不存在，则该字符被加入集合。
当整个字符串遍历完毕后，集合中的元素就是所有出现过的不同字符。
因此，集合的大小（即集合中元素的个数）就是我们要求的答案。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    set<char> unique_chars;
    for (char c : s) {
        unique_chars.insert(c);
    }
    cout << unique_chars.size() << endl;
    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        Set<Character> uniqueChars = new HashSet<>();
        for (char c : s.toCharArray()) {
            uniqueChars.add(c);
        }
        System.out.println(uniqueChars.size());
    }
}

n = int(input())
s = input()
print(len(set(s)))

算法及复杂度

算法：使用集合（Set）进行去重计数。
时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 是字符串的长度。我们需要遍历一次字符串，每次向集合中插入元素的平均时间复杂度为 $\mathcal{O}(1)$ （对于哈希集合）或 $\mathcal{O}(\log k)$ （对于平衡树集合，其中 $k$ 为集合大小）。
空间复杂度： $\mathcal{O}(k)$ ，其中 $k$ 是不同字符的数量。最坏情况下，所有字符都不同，空间复杂度为 $\mathcal{O}(n)$ 。但由于字符集大小是有限的（大小写字母+数字），空间复杂度也可以认为是 $\mathcal{O}(|\Sigma|)$ ，其中 $|\Sigma|$ 是字符集的大小，是一个常数。