密码强度——解决人类最大的悲痛

Question

• [题目描述 ]
  人间一大悲痛是密码强度过低防不住盗号，密码强度过高记不住把自己防了。所以有一次你想到了这样一种方法来搞一个靠谱一点的密码：

首先你在一个文档里脸滚键盘随机输入了一大串小写字母，然后你要节选其中满足以下条件的一些字母来构成一个字符串作为你的高强度密码：

1、选出的字母不能有重复，因为相同的重复字符不会增强密码。也就是说不能同时出现两个字母𝑎或两个字母𝑏等等。

2、在1的前提下，要保持选出的字母的内部顺序在原串和新字符串中没有变化，以方便记忆。

3、在1和2的前提下，要求选出的字母尽量多也就是字符串尽量长，以增强密码强度。

4、在1和2和3的前提下，要求你选出的字符串字典序尽量小，以保证唯一性。

现在给出你脸滚键盘的产物，请据此推断出你的密码。

• [输入格式 ]
  一行一个字符串，表示原字符串。

• [输出格式 ]
  一行一个字符串，表示密码。

输入
bbcaac
输出
bac

• [数据范围与提示]
  对于10%的数据，原串满足条件1。

对于20%的数据，𝑛 ≤ 5。

对于30%的数据，𝑛 ≤ 10。

对于40%的数据，𝑛 ≤ 20。

对于70%的数据， 𝑛 ≤ 10^3。

对于100%的数据，n ≤ 10^6，保证字符串均由小写英文字母构成。

上述𝑛表示原字符串的长度

满足 1 的有𝑎, 𝑏, 𝑐, 𝑎𝑏, 𝑎𝑐, 𝑐𝑎, 𝑏𝑎, 𝑏𝑐, 𝑐𝑏, 𝑎𝑏𝑐, 𝑎𝑐𝑏, 𝑏𝑎𝑐, 𝑏𝑐𝑎, 𝑐𝑎𝑏, 𝑐𝑏𝑎

满足 2 的有𝑎, 𝑏, 𝑐, 𝑎𝑐, 𝑐𝑎, 𝑏𝑐, 𝑏𝑎, 𝑏𝑐𝑎, 𝑏𝑎𝑐

满足 3 的有𝑏𝑐𝑎, 𝑏𝑎𝑐

满足 4 的是𝑏𝑎𝑐

Answer 1

题目描述这么一大坨,.其实就是要字符串去重并且字典序最小
你题目的解答代码如下：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    vector<int> num(26), vis(26);
    for (char ch : s)
        num[ch - 'a']++;
    string res;
    for (int i = 0; i < s.size(); ++i)
    {
        if (vis[s[i] - 'a'] == 1)
        {
            num[s[i] - 'a']--;
            continue;
        }
        while (!res.empty() && res.back() > s[i] && num[res.back() - 'a'] > 1)
        {
            num[res.back() - 'a']--;
            vis[res.back() - 'a'] = 0;
            res.pop_back();
        }
        res.push_back(s[i]);
        vis[s[i] - 'a'] = 1;
    }
    cout << res << endl;
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!