Similar Name

Hard

0/120

Average time to solve is 30m

Contributed by

0 upvote

Problem statement

Being a class monitor, you have a list of names of your class students. Your task is to find the first name from the list, which is similar to any other name occurring before it in the list.

Two names, name1 and name2, are similar if at least one of the following conditions holds.

Both names are identical.
name1 is a prefix of name2.
name2 is a prefix of name1.

Print the first name from the list, which is similar to any other name present in the prefix part of the list. If no such name is found, print “not found”.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains 'T', denoting the number of tests.
For each Test :
    The first line contains one integer 'N', denoting the number of names in the list.
    Next 'N' lines contain one string each, denoting the names in the list.

Output Format:

For each test, print one string, denoting the first name in the list, similar to another name in the prefix part of the list. If no such name is found, print “not found”.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= the length of name[i] <= 60   i ∈  (1,N)
All letters in name[i] are lowercase english letters, in the range 'a' to 'j' inclusive.
Note - Sum of 'N' over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input 1 :

2
4
aab
aac
aacgh
aabgh
3
abc
aba
baa

Sample Output 1 :

aacgh
not found

Explanation for Sample Input 1 :

For case 1:
    Start checking from the first name to the last.
    For "aab", a similar name is "aabgh", but that's not present in the prefix list.
    For "aac", a similar name is "aacgh", but that’s also not present in the prefix of list.
    For "aacgh", similar name is "aac" which is present in prefix of list. Hence our answer is "aacgh".

For Case 2:
    No name in the list is similar to any other name. Hence print "not found".

Sample Input 2 :

2
3
ab
abb
abbb
2
dc
d

Sample Output 2 :

abb
d

Console