You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
45 lines
1.0 KiB
45 lines
1.0 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 26;
|
|
// acdaccdd
|
|
unordered_set<char> S; //有哪些字符
|
|
bool st[N]; //是不是使过了
|
|
string res; //结果，字典序最小
|
|
string s; //原始串
|
|
string t;
|
|
void dfs(int u) {
|
|
//出口
|
|
if (u == s.size()) {
|
|
if (t.size() == S.size())
|
|
if (t < res) res = t; // t<res
|
|
return;
|
|
}
|
|
//没有使过
|
|
if (!st[s[u] - 'a']) {
|
|
//使上
|
|
st[s[u] - 'a'] = true;
|
|
t.push_back(s[u]);
|
|
//下一个
|
|
dfs(u + 1);
|
|
//回溯
|
|
t.pop_back();
|
|
st[s[u] - 'a'] = false;
|
|
}
|
|
//使过或者没使过但不想使，都走这条路径
|
|
dfs(u + 1);
|
|
}
|
|
|
|
int main() {
|
|
//初始化极大值
|
|
for (int i = 0; i < 200; i++) res = res + 'z';
|
|
//读入字符串
|
|
cin >> s;
|
|
//去重形成一个集合
|
|
for (int i = 0; i < s.size(); i++) S.insert(s[i]);
|
|
//深搜
|
|
dfs(0);
|
|
//输出
|
|
cout << res << endl;
|
|
return 0;
|
|
} |