解题思路

输入只由 a~z 这 26 个小写字母组成，要去掉重复的字母，并且按英文字母顺序输出。

因为字母的种类只有 26 个，我们可以准备一张“打钩表” vis[26]：

• vis[0] 对应字母 a，vis[1] 对应字母 b，……，vis[25] 对应字母 z；
• 某个字母在字符串里出现过，就把对应的格子打上钩（变成 true）。

做法：

1. 遍历字符串，遇到字母就把 vis[字母-'a'] 标记为 true。同一个字母出现很多次，也只是打个钩，这就实现了去重；
2. 输出的时候，从 a 到 z 依次看哪个格子打了钩，打了钩就输出这个字母。因为是从小到大扫的，所以输出自然就是按英文字母顺序了。

用样例验证：babcccxyz 里出现过的字母有 a、b、c、x、y、z，按顺序输出 abcxyz，和样例一致。

参考代码

// P4559 字符串去重：去掉重复字母，按英文字母顺序排列输出
#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool vis[26] = {false};    // 记录a~z每个字母是否出现过
    for (int i = 0; i < s.size(); i++)
        vis[s[i] - 'a'] = true; // 把出现的字母标记为true
    string ans;
    // 按字母顺序a~z输出所有出现过的字母，自然就排好序了
    for (int c = 0; c < 26; c++)
        if (vis[c]) ans += char('a' + c);
    cout << ans << endl;
    return 0;
}

复杂度分析

• 遍历一遍字符串打钩是 O(L)，再扫 26 个格子输出，只有常数时间。
• 总时间复杂度 O(L + 26)，L 是字符串长度（不超过 1000）；空间复杂度 O(26)，即常数 O(1)。