Problem

Submissions

Hints & solutions

Discuss

Similar Name

Hard

0/120

Average time to solve is 30m

Contributed by

2 upvotes

Asked in companies

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

Hint 1

Hint 2

Can you check for each pair of names?

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach: Run two loops (nested) to find all possible pairs of names and check similarity between them. If a pair at index (i, j) is similar where (i < j), then the name at index ‘j’ is the answer for such a pair. Finally, return the name with minimum ‘j’ among all generated pairs.

Algorithm:

Iterate a for loop, j = 1 to N.
- Iterate another for loop, i = 1 to j-1.
  - If any of the following conditions hold.
    - [i-th name] is a prefix of [j-th name].
    - [j-th name] is a prefix of [i-th name].
    - Both names are identical.
  - Return [j-th name] from the list.
Return “not found”.

Time Complexity

O(N * N * len), where ‘N’ is the number of names in the list and ‘len’ is the average length of names.

We make N*N pairs of names and check similarity in one pair costs O(len). Hence overall time complexity becomes O(N * N * len).

Space Complexity

O(1).

We are using only constant space. Hence overall space complexity is O(1).

(100% EXP penalty)

Similar Name

Console