https://www.codechef.com/MACE2021/problems/MCODE01

PROBLEM LINK: Contest Page | CodeChef

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

#include

#include

#include

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