Last Updated: 30 Oct, 2021
Complete String
Hard
Asked in companies
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.
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
Approaches
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.
Approach :
- We will use Trie to solve this problem.
- Trie will have two properties :
- Next pointer to link the next character of the string.
- Ending flag to denote if this is the last character of some string.
- We will store each string in the trie.
- Now we traverse the trie in dfs manner.
- If while traversing , each level till now has the ending flag set on, then that means till this string, all prefixes of the string are present in the array ‘A’.
- So, we check the maximum length strings that satisfy the above condition.
- Example :
- Let N = 4 and A[] = [“j”, “ji” , “jin” , jxn” ].
- The trie structure will look like this :
- We can notice that the ending at character ‘x’ is 0, as the word “jx” is not present in array ‘A’.
- So, we traverse from ‘j’ to ‘ji’ to ‘jin’ and since the ending is 1, all are valid strings.
- Since we want the longest among these, we select “jin”.
- When we traverse from ‘j’ to ‘jx’ , we encounter ending 0 which tells that this and the further depth strings are not valid, so we don’t need to traverse to ‘jxn’.
- So, “jin” is the desired answer.
Algorithm :
- Initialise a class ‘Trie’ with ‘next’ and ‘ending’ as objects.
- Traverse the array ‘A’ and insert each string in the trie.
- Initialize a variable ‘ans’ as “”.
- Now, traverse the trie in Depth First Search Manner.
- Initialize a variable ‘flag’ as ‘1’.
- If while traversing, any node has ‘ending flag’ as 0, then we return to avoid more depth searches.
- Else, all the prefixes till now are present in array ‘A’.
- If the string formed till now is larger than ‘ans’, update ‘ans’.
- If the string formed till now is of the same length as that of ‘ans’, update ‘ans’ as the minimum of the two. ( To return lexicographically smallest string )
- If ‘ans’ is empty, then update “ans” to “None”.
- Return ‘ans’ as the final result.