Topics

# 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.
``````
Detailed explanation ( Input/output format, Notes, Images )
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
``````
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