Creating Strings
Enumerate every distinct permutation of the given string in lexicographic order.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Given a string that may contain repeated characters, list every distinct permutation in lexicographic order and print how many such permutations there are.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The duplicates are the only complication. If every character were distinct, ordinary permutation generation would be enough. With repeated characters, we must avoid printing the same arrangement more than once.
Sorting the string first solves both requirements at once:
the first arrangement becomes the lexicographically smallest one
repeated calls to
next_permutationvisit each distinct arrangement in sorted orderThis works because equal characters are indistinguishable. Starting from the sorted string ensures the algorithm walks through the multiset permutations without manual deduplication tables.
Since the input is small, storing all permutations before printing them is completely reasonable and makes it easy to print the count first.
Pseudocode
Natural algorithm flow before dropping to the concrete C++ implementation.
Sort the string.
Create an empty list of answers.
Do:
add the current string to the answer list
while another lexicographically larger permutation exists.
Print the number of stored strings, then print each one.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(k \cdot n)\), where \(k\) is the number of distinct permutations
Memory: \(O(k \cdot n)\) when storing the permutations before printing
C++ Solution
The exact repository source used for this solution page.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string s;
std::cin >> s;
std::sort(s.begin(), s.end());
std::vector<std::string> permutations;
do {
permutations.push_back(s);
} while (std::next_permutation(s.begin(), s.end()));
std::cout << permutations.size() << '\n';
for (const std::string& permutation : permutations) {
std::cout << permutation << '\n';
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
For this problem size, the output dominates everything else, so a simple library-based permutation loop is the right tradeoff.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.