最少相異字母

題解

我們可以利用set去讓重複字消失，並且只記錄有出現過那些字，取其長度之後，去跟min_l做比較，我有三種情況:

• 1.$min_l<length$ 無事發生，無須執行
• 2.$min_l>length$ 把length更新為新的最小相異字母數，並且更新紀錄哪個字為最小字典序的
• 3..$min_l=length$ 比較兩個字典序的大小，並且更新記錄最小字典序的

AC Code

python

from sys import stdin
n=int(stdin.readline().strip())
min_l=float('inf')
out=[]
for i in range(n):
    x=stdin.readline().strip()
    length=len(set(x))
    if length<min_l:
        min_l=length
        out=[x]
    elif length==min_l:
        out.append(x)
data=sorted(out)
print(data[0])

C++

#include<bits/stdc++.h>
using namespace std;
int count_distinct(const string& s){
    set<char> distinct_chars;
    for(char c : s){
        distinct_chars.insert(c);
    }
    return distinct_chars.size();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    int min_l = INT_MAX;

    string best_s="";

    for(int i=0;i<n;i++){
        string x;
        cin>>x;
        int length=count_distinct(x);
        if(length<min_l){
            min_l=length;
            best_s=x;
        }else if(length==min_l){
            if(x<best_s){
                best_s=x;
            }
        }
    }
    cout<<best_s<<endl;
    return 0;
}