题意

给定一个仅含小写字母的字符串

每个测试有多组数据，每个数据字符串长度不大于20

方法

枚举

我们先枚举小写字母,每次枚举遍历字符串,统计该小写字母的出现次数.

并使用变量记录最小的出现次数以及对应的字母们

以样例数据 aabbcddd 为例

这样我们就能知道哪些字母出现的次数最少

最后遍历字符串s,如果位置上的字符是最小出现次数的则不要输出它即可.

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

char s[30];

int main(){
    while(~scanf("%s",s)){
        int n = strlen(s);
        int minc = 0x3f3f; // 最小次数
        vector<char> minch = {}; // 对应的字母们
        rep(ch,'a','z'+1){ // 枚举字母
            int cnt = 0;
            rep(i,0,n){
                cnt += s[i] == ch; // 统计次数
            }
            if(cnt == 0)continue; // 字母未出现
            if(cnt < minc){ // 比最小次数的还小
                minc = cnt;
                minch = {};
                minch.push_back(ch);
            }else if(cnt == minc){ // 和最小的次数一样
                minch.push_back(ch);
            }
        }
        rep(i,0,n){
            bool ismin = false;
            for(auto ch:minch){
                if(ch == s[i])ismin = true; // 该字母是否是最小次数的字母
            }
            if(ismin)continue;
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 我们遍历了所有小写字母,每个字母遍历了字符串,以此得到最小次数的字母.随后我们遍历字符串,对字符串每个字符检查它是否是最小次数的字母决定是否输出.其中小写字母个数为常数,而字符串长度为$nn$n,因此总时间复杂度为$O\left(n\right)O(n)$O(n)

空间复杂度: 我们主要用了数组来保存读入的字符串$O\left(n\right)O(n)$O(n),用了一个额外数组来记录出现次数最小对应的字母们,小写字母最大的个数是常数,所以总空间复杂度为$O\left(n\right)O(n)$O(n)

一次性统计

我们可以用数组cnt 把每个字符出现的次数存起来

再找到出现最小的次数

再次遍历时比较是否是出现次数最小的,如果是最小的则不输出

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

char s[30];

int main(){
    while(~scanf("%s",s)){
        int n = strlen(s);
        vector<int> cnt(30,0); 
        rep(i,0,n){
            cnt[s[i]-'a']++;// 记录每个字符出现的次数
        }
        int minc = 0x3f3f;
        rep(i,'a','z'+1){
            if(!cnt[i-'a'])continue; // 忽略个数为0的
            minc=min(minc,cnt[i-'a']); // 计算最小的次数
        }
        rep(i,0,n){
            if(cnt[s[i]-'a'] == minc)continue; // 如果是最小的 则"删除"
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

设字符串长度为$nn$n

时间复杂度: 我们遍历了字符串两次，分别统计和输出。另外我们遍历了字符从'a'到'z'寻找最小的次数,所以总时间复杂度为$O\left(n\right)O(n)$O(n)

空间复杂度: 我们主要使用了一个 字符次数统计的常数大小的数组，和字符串长度无关，另外一个数组储存了读入的字符串，所以总空间复杂度为$O\left(n\right)O(n)$O(n)