PAT(Advanced Level)A1112. Stucked Keyboard

题意

键盘上有按键坏了，要是按下去一定会重复K次，现在要根据字符串找到所有可能坏掉的按键

思路

• 统计每个字符出现的次数，比如eee_eeeeee，就会统计e曾经出现过[3, 6]次
• 检查字符串出现的每个字符，看出现的次数是否都为k的倍数，如果是，就可以肯定这个按键坏掉了。要输出坏掉的按键，我这里处理的方法比较笨，在一开始的时候读入记住索引排序后输出
• 接下来根据按键是否坏掉来重新整理输入的字符串

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    unordered_map<char, vector<int>> cnt;
    unordered_map<char, int> first_cur;
    for(int i = 0; i < s.size(); i++) {
        int tmp = 0, j = i + 1;
        while(j < s.size() && s[j] == s[i]) j++;
        int same_cnt = j - i;
        i += same_cnt - 1;
        if(first_cur[s[i]] == 0)
            first_cur[s[i]] = i;
        cnt[s[i]].emplace_back(same_cnt);
    }
    unordered_set<char> ss;
    for(auto it: cnt) {
        bool judge = true;
        for(auto e: it.second) {
            if(e % k != 0) {
                judge = false;
                break;
            }
        }
        if(judge)
            ss.insert(it.first);
    }
    vector<char> ans;
    for(auto i: ss) {
        ans.emplace_back(i);
    }
    sort(ans.begin(), ans.end(), [&](char x, char y) {
        return first_cur[x] < first_cur[y];
    });
    for(auto i: ans)    cout << i;
    cout << endl;
    for(int i = 0; i < s.size(); i++) {
        if(ss.find(s[i]) != ss.end()) {
            int tmp = 0, j = i + 1;
            while(j < s.size() && s[j] == s[i]) j++;
            int factor = (j - i) / k;
            while(factor--) cout << s[i];
            i += (j - i) - 1;
        }else
            cout << s[i];
    }
    return 0;
}