PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY: EASY
PREREQUISITES:
None
PROBLEM:
You are given N strings S1, S2, S3, …… SN. All these strings are related to each other by some factor. For any 2 strings Si and Sj, The relation factor between them is the length of the largest common prefix. i.e. the number of common characters in the beginning. ( For two strings “ Hello” and “Hey”, their relation factor is 2 as “He” is the common prefix with the maximum length.) If two strings do not have any common characters in the beginning, then their relation factor is 0. Your task is to find the maximum relation factor possible between any two strings.
#QUICK EXPLANATION:
Sort the strings, and find the maximum relation factor between any two adjacent strings.
#EXPLANATION:
One way is to find all the possible pairs and find the largest factor among them. But that is not an effective method.
We should understand that the 2 strings having the highest relation factor will always lie close when arranged in ascending/descending order.
So we just have to sort the strings and find the relation factor of each neighbor. The highest among those will be the answer.
SOLUTIONS:
Setter's Solution
using namespace std;
void solve(){
int n;
cin>>n;
string s[n];
for(int i=0;i<n;i++)
{
cin>>s[i];
}
sort(s,s+n);
int max=0,factor;
for(int i=0;i<n-1;i++)
{
factor=0;
for(int j=0;j<min(s[i].length(),s[i+1].length());j++)
{
if(s[i][j]!=s[i+1][j])
{
break;
}
else
{
factor++;
}
}
if(factor>max)
max=factor;
}
cout<<max;
cout<<“\n”;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
solve();
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person