Creating Strings
You are given a string. Generate all distinct strings that can be created by reordering its characters.
Constraints:
- \(1 \le n \le 8\), where \(n\) is the length of the string
- The string contains only the characters
a–z.
Input:
- One line: the string.
Output:
- First line: integer \(k\) — the number of distinct strings.
- Next \(k\) lines: the strings in alphabetical order.
Example:
Input:
aabac
Output:
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa
Solution
We build the strings with backtracking, one character at a time. If we chose a position of the original string at each step, equal characters would give the same string several times: aabac has \(5! = 120\) orders of its positions, but only \(20\) distinct strings.
So instead of positions we choose letters. We count how many copies of each letter the string has. At each step we try every letter that still has an unused copy, use one copy, continue, and then undo the step. Each distinct string is built exactly once, because two different choices at the same step put different letters at the same position.
We try the letters from a to z, so the strings are created in alphabetical order.
There are at most \(8! = 40320\) strings, so the backtracking is fast.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int n;
int available[26]; // how many copies of each letter are still unused
string current;
vector<string> result;
void backtracking() {
// all letters are used, record the string
if ((int) current.size() == n) {
result.push_back(current);
return;
}
// try each letter that is still available, in alphabetical order
for (int c = 0; c < 26; c++) {
if (available[c] == 0) {
continue;
}
available[c]--;
current.push_back('a' + c);
backtracking();
current.pop_back(); // undo the step
available[c]++;
}
}
int main() {
string s;
cin >> s;
n = s.size();
for (char ch : s) {
available[ch - 'a']++;
}
backtracking();
cout << result.size() << "\n";
for (string t : result) {
cout << t << "\n";
}
}