Most Frequent Distinct-Letter Subsequence
Autumn Tournament (2019)
Submission name: long.cpp
Problem summary
Choose a length-K subsequence with no repeated letter. Find the largest number of input strings that can all supply this same subsequence. Print that maximum, the lexicographically smallest winning subsequence, and how many different subsequences attain the maximum. A string contributes at most once even if it contains many embeddings.
Input
N M K, then N strings over the first M lowercase Latin letters.
Output
The maximum frequency, a smallest winning subsequence, and the number of winning subsequences on separate lines. Print only 0 if no candidate occurs.
Constraints
Four independent groups: N<10000,M<27,K=1,|S|<99; or N<1500,M<20,K<4,|S|<99; or N<500,M<18,K<5,|S|<39; or N<100,K<M<9,|S|<19. Memory limit 32 MB.
Worked example
Original statement sample.
Input
5 7 2 fagcbdaga dcdfb acfebdc cfc cegdb
Output
4 cb 2
Solution analysis
- Every possible candidate is an ordered selection of K different letters from M: there are Q=M!/(M−K)! candidates. Generate them lexicographically by a recursive search that never reuses a letter. The four constraint groups keep Q manageable: the maximum is 57120.
- For one input string, build next[pos][letter], the first occurrence at or after pos, or the string length when absent. A candidate is a subsequence exactly when repeatedly jumping to the next required letter succeeds. This costs O(K) per candidate, independent of the string length. Process input strings one at a time and increment a candidate’s counter once after a successful whole match.
- In the sample, cb occurs as a subsequence in fagcbdaga, dcdfb, acfebdc and cegdb, so its frequency is four. cd also occurs in four strings. No candidate occurs more often; cb is smaller than cd, so print 4, cb, 2. Multiple embeddings of cb in one string do not create extra contributions.
Why it works
Greedy next-occurrence matching leaves as much unused suffix as possible after every chosen letter, so it succeeds exactly for subsequences. Every distinct-letter length-K candidate is generated once. Its counter therefore equals exactly the number of input strings containing it. Taking the maximum, first lexicographic winner and number of tied candidates gives all requested outputs.
Watch out. Count strings, not embeddings. Different letters are required inside a candidate. The third output counts tied candidate strings, not ways to select positions. Avoid storing next tables for every input string, especially in the large K=1 group.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Greedy next-occurrence matching leaves as much unused suffix as possible after every
// chosen letter, so it succeeds exactly for subsequences. Every distinct-letter length-K candidate is
// generated once.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void generate(int alphabet,int needed,vector<bool>&used,string¤t,vector<string>&candidates){
if(static_cast<int>(current.size())==needed){
candidates.push_back(current);
return;
}
for(int letter=0;letter<alphabet;letter++){
if(!used[letter]){
used[letter]=true;
current.push_back(static_cast<char>('a'+letter));
generate(alphabet,needed,used,current,candidates);
current.pop_back();
used[letter]=false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int alphabet;
int needed;
cin>>n>>alphabet>>needed;
vector<string>candidates;
vector<bool>used(alphabet,false);
string current;
generate(alphabet,needed,used,current,candidates);
vector<int>frequency(candidates.size(),0);
for(int item=0;item<n;item++){
string text;
cin>>text;
int length=static_cast<int>(text.size());
vector<vector<int>>next(length+1,vector<int>(alphabet,length));
for(int position=length-1;position>=0;position--){
next[position]=next[position+1];
next[position][text[position]-'a']=position;
}
for(size_t candidate=0;candidate<candidates.size();candidate++){
int position=0;
bool matches=true;
for(char letter:candidates[candidate]){
int found=next[position][letter-'a'];
if(found==length){
matches=false;
break;
}
position=found+1;
}
if(matches){
frequency[candidate]++;
}
}
}
int best=0;
int winners=0;
string smallest;
for(size_t candidate=0;candidate<candidates.size();candidate++){
if(frequency[candidate]>best){
best=frequency[candidate];
winners=1;
smallest=candidates[candidate];
}
else if(frequency[candidate]==best&&best>0){
winners++;
}
}
if(best==0){
cout<<0<<'\n';
}
else{
cout<<best<<'\n';
cout<<smallest<<'\n';
cout<<winners<<'\n';
}
}