Complete String

Hard
0/120
Average time to solve is 40m
profile
Contributed by
241 upvotes
Asked in companies
SprinklrThought WorksBNY Mellon

Problem statement

Ninja developed a love for arrays and strings so this time his teacher gave him an array of strings, ‘A’ of size ‘N’. Each element of this array is a string. The teacher taught Ninja about prefixes in the past, so he wants to test his knowledge.

A string is called a complete string if every prefix of this string is also present in the array ‘A’. Ninja is challenged to find the longest complete string in the array ‘A’.If there are multiple strings with the same length, return the lexicographically smallest one and if no string exists, return "None".

Note : 
String ‘P’ is lexicographically smaller than string ‘Q’, if : 

1. There exists some index ‘i’ such that for all ‘j’ < ‘i’ , ‘P[j] = Q[j]’ and ‘P[i] < Q[i]’. E.g. “ninja” < “noder”.

2. If ‘P’ is a prefix of string ‘Q’, e.g. “code” < “coder”.
Example : 
N = 4
A = [ “ab” , “abc” , “a” , “bp” ] 

Explanation : 

Only prefix of the string “a” is “a” which is present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “ab” are “a” and “ab” both of which are present in array ‘A’. So, it is one of the possible strings.

Prefixes of the string “bp” are “b” and “bp”. “b” is not present in array ‘A’. So, it cannot be a valid string.

Prefixes of the string “abc” are “a”,“ab” and “abc” all of which are present in array ‘A’. So, it is one of the possible strings.

We need to find the maximum length string, so “abc” is the required string.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The second line of each test case contains an integer ‘N’ denoting the size of array ‘A’.

The third line of each test case contains ‘N’ space-separated strings denoting the elements of array ‘A’.
Output format : 
For each test case, print the longest string in ‘A’, such that every prefix of this string is also present in the array ‘A’. If there are multiple strings with the same length, return the lexicographically smallest one and if no string exists, return "None" as answer.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i].length <= 10^5
A[i] only consists of lowercase english letters.
Sum of A[i].length <= 10^5 over all test cases

Time Limit : 1 sec
Sample Input 1 :
2
6
n ni nin ninj ninja ninga
2
ab bc
Sample Output 1 :
ninja
None
Explanation Of Sample Input 1 :
For test case 1 we have, 

All the prefixes of “ninja” -> “n”, “ni”, “nin”, “ninj” and “ninja” are present in array ‘A’. So, “ninja” is a valid answer whereas for “ninga” , the prefix “ning” is not present in array ‘A’.

So we output “ninja”.

For test case 2 we have, 

The prefixes of “ab” are “a” and “ab”. “a” is not present in array ‘A’. So, “ab” is not a valid answer.

The prefixes of “bc” are “b” and “bc”. “b” is not present in array ‘A’. So, “ab” is not a valid answer.

Since none of the strings is a valid answer we output “None”.
Sample Input 2 :
2
5
g a ak szhkb hy 
4
kez vfj vfjq vfjqo
Sample Output 2 :
ak
None
Hint

Try finding the prefix of each string and checking if they exist in the array.

Approaches (2)
Brute Force

 

Approach : 
 

  • We first find all the prefixes of each string in array ‘A’.
  • For each string ‘S’, we check if all the prefixes are part of the array ‘A’.
  • To check this, we mark the strings of array ‘A’ in a map.
  • If there are no such strings, we return “”.
  • We select the largest length string that has all prefixes in ‘A’.
  • We sort all the strings that satisfy the above criteria and return the lexicographically smallest one.


 

Algorithm : 
 

  • Initialise a variable ‘ans’ as “”.
  • Initialise a hashmap ‘m’ with key type string and value type integer.
  • Traverse over all the strings ‘s’ of array ‘A’ and mark ‘m[s] = 1’.
  • Traverse over all the strings ‘s’ of array ‘A’ again :
  • Initialise a variable ‘flag’ as ‘1’.
  • If the size of current string is ‘sz’, run a loop from ‘i=0’ to ‘i=sz-1’ :
    • Find the prefix ‘p’ of ‘s’ from index ‘j=0’ to ‘j=i’ and check if it is marked in the map ‘m’.
    • If not, mark ‘flag’ as 0.
  • If the ‘flag’ = 1 :
    • Check if current string ‘s’ is greater in size than ‘ans’ :
    • If yes, update ‘ans’ to ‘s’.
    • Else, if current string ‘s’ is same in length to ‘ans’ :
    • Update ‘ans’ to the minimum of ‘ans’ and ‘s’.
  • If ‘ans’ is empty, then update “ans” to “None”.
  • Return ‘ans’ as the final result.
Time Complexity

O(Sum(A[i])*max(A[i])*log(N)), where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’, max(A[i]) is the maximum length of string in array ‘A’ and ‘N’ is the size of array ‘A’.
 

We are finding the prefixes of all strings ,searching them in a map, so the overall time complexity is O(Sum(A[i])*max(A[i])*N).

 

Space Complexity

O(Sum(A[i])) where ‘Sum(A[i])’ is the sum of length of all words ‘A[i]’.

 

We are storing all strings in a map. Hence, the overall Space Complexity is O(Sum(A[i])).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Complete String
Full screen
Console