Common Rearranged Substring
Autumn Tournament (2014)
Submission name: substring.cpp
Problem summary
You may independently rearrange two lowercase strings. Find the longest string that can occur as a contiguous substring of both rearrangements. Among maximum-length answers, print the lexicographically smallest.
Input
Two lowercase strings on separate lines.
Output
The required string on one line; an empty line if no letter is shared.
Constraints
Each string has at most 1000 characters.
Worked example
Original statement sample.
Input
autumn tournament
Output
amntu
Solution analysis
- Rearranging removes all restrictions on original positions. A candidate substring can be placed at the beginning of a rearrangement precisely when it uses no more copies of any letter than the original string contains.
- Count each of the 26 letters in both strings. The common substring can use at most min(countA[c],countB[c]) copies of letter c. Taking this many copies of every letter maximizes its length.
- To make that maximum-length answer lexicographically smallest, output its letters in alphabetical order. In autumn and tournament the shared counts give one each of a, m, n, t, u, hence amntu. The extra t in tournament cannot be used because autumn has only one.
Why it works
Every answer is bounded independently by the smaller frequency of each letter. Taking every such available occurrence meets all bounds simultaneously and can be embedded in both rearrangements. No longer answer is possible. Sorting these chosen letters gives their smallest lexicographic permutation.
Watch out. This is not the ordinary longest common substring or subsequence problem: arbitrary permutations are allowed. Preserve repeated letters up to their shared counts. No common letters means an empty output line.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every answer is bounded independently by the smaller frequency of each letter. Taking
// every such available occurrence meets all bounds simultaneously and can be embedded in both
// rearrangements.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
string first;
string second;
cin>>first>>second;
array<int,26>countFirst{};
array<int,26>countSecond{};
for(char letter:first){
++countFirst[letter-'a'];
}
for(char letter:second){
++countSecond[letter-'a'];
}
for(int index=0;index<26;++index){
int copies=min(countFirst[index],countSecond[index]);
cout<<string(copies,static_cast<char>('a'+index));
}
cout<<'\n';
}