Order-equivalent Words
National Olympiad — Regional round
Submission name: congruence.cpp
Problem summary
Two uppercase words are equivalent when every pair of positions has the same comparison (<, = or >) in both. Find the lexicographically smallest and largest words equivalent to the input.
Input
One nonempty uppercase Latin word.
Output
The smallest word, then the largest word, on separate lines.
Constraints
Length ≤ 15000000.
Worked example
An independently prepared example for this explanation.
Input
CADC
Output
BACB YXZY
Solution analysis
- Rank the distinct input letters in alphabetical order.
- Map ranks to the first d letters for the minimum and the last d letters for the maximum, where d is the number of distinct letters.
Why it works
An equivalent word assigns strictly increasing distinct letters to the d ranks. Rank r cannot be below r or above 26-d+r. The two mappings attain these bounds simultaneously, hence are lexicographically extremal.
Watch out. Preserve equality as well as order; do not simply shift the original alphabet letters.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: An equivalent word assigns strictly increasing distinct letters to the d ranks. Rank r
// cannot be below r or above 26-d+r.
#include<iostream>
#include<string>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin>>s;
int used[26]={},rank[26],d=0;
for(char c:s){
used[c-'A']=1;
}
for(int i=0;i<26;i++){
if(used[i]){
rank[i]=d++;
}
}
for(char c:s){
cout<<char('A'+rank[c-'A']);
}
cout<<'\n';
for(char c:s){
cout<<char('A'+26-d+rank[c-'A']);
}
cout<<'\n';
}