PROBLEM LINK: Contest Page | CodeChef
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
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.
Sort the strings, and find the maximum relation factor between any two adjacent strings.
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.
using namespace std;