Find the largest matching word.

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
WalmartSAP LabsGoogle inc

Problem statement

You have been given a string ‘ST’ of length ‘N’ and ‘X’ words all containing lowercase alphabets. You call a word matching from ‘ST’ if by removing some characters of ‘ST’ you can form that word.

Your task is to return the largest matching word among these ‘X’ words. If there are multiple strings of largest length return lexicographically smallest string. If no word matches from ‘ST’ return ‘#’ as the string.

Example: 
Let’s say you have “abcd” as string ‘ST’ and 2 words “bd” and “db”. “bd” matches with the string ‘ST’ as you can remove ‘a’ and ‘c’ character to form “bd”. “db” does not match with the string ‘ST’ because it is impossible to form “db” from the string ‘ST’ by removing characters.
Note: 
You cannot change the order of characters in ‘ST’ after removing some characters.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two single space-separated integers ‘N’ and ‘X’ representing the length of string ‘ST’ and number of words respectively.

The second line contains the string ‘ST’.

Each of the next ‘X’ lines contains ‘X’ words.
Output Format: 
For each test case, return the largest matching word among these ‘X’ words. If there are multiple strings of largest length return lexicographically smallest string. If no word matches from ‘ST’ return ‘#’ as the string.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 100
1 <= X <= 100

Time Limit: 1 sec
Sample Input 1:
2
4 2
abcd  
bd
cd
4 2
efcd  
bdf
db
Sample Output 1:
bd
#

Sample Output 1 Explanation:

Test case 1:

Matching from ‘st’ for each word:-
“bd” matches with string as we can remove ‘a’ and ‘c’ from the string ‘ST’ to form “bd”.
“cd” matches with string as we can remove ‘a’ and ‘b’ from the string ‘st’ to form “cd”.

Therefore the answer is “bd” as it is the longest matching word. “cd” is of the same length but “bd” is lexicographically smaller.


Test case 2:

Matching from ‘ST’ for each word:-
“bdf” does not match with string as ‘st’ does not contains ‘b’.
“db” does not match with string as ‘st’ does not contains ‘b’.

Therefore the answer is “#” as no word matches from the string ‘st’.
Sample Input 2:
2
4 2
dacb  
ac
dcb
4 2
efcd  
fd
ef
Sample Output 2:
dcb
ef
Hint

Find all words that can be formed from ‘st’.  

Approaches (2)
Brute Force

We will first find all the words that can be formed by removing some characters from ‘ST’ and then for each of 'X' words we will check if it can be formed from ‘ST’.

We maintain an unordered set( hashmap ) that stores all the words that can be formed from 'S'. We write a recursive function ‘FORM_WORD(int idx, string S, string W)’ to find all the words that can be formed from ‘ST’:-

 

  • ‘idx’ represents the character of ‘ST’ for which we need to make a choice to keep or remove. 'W' stores the word that has been formed till now.
  • We will call recursive ‘FORM_WORD(0, ‘ST’ , “ ”)’ as we will start from the 1st character at 0th position. Since no character has been taken yet, w is “”.
  • At each particular ‘idx’ in recursion do as follows:-
    • If ‘idx’ == N’ We have reached the end of the ‘ST’. Check if 'W' is non-empty. If yes then insert it in the unordered set.
  • Else There are two cases:-
    • We don’t take the current character and recursively call ‘form word(‘idx’+1, ‘ST’, 'W')’.
    • We take the current character in word 'W' i.e. we append ST[i] to 'W' and call ‘form word(‘idx’+1, ‘ST’, 'W')’.

 

For each word:-

  • Check if the word is present in an unordered set. If the word is present in unordered set:-
    • If current word length is greater than the length of ‘ANS’, initialize ‘ANS’ with this word.
    • If current word length is equal to the length of ‘ANS’. If the current word is lexicographically smaller than ‘ANS’, initialize ‘ANS’ with this word.
  • If ‘ANS’ is empty after checking with all the words initialize ANS with “#”.
  • Return ‘ANS’.
Time Complexity

O(N*2^N), where ‘N’ denotes the length of string ‘ST’.

 

We form all possible words that can be formed from ‘ST’.

Space Complexity

O(N*2^N), where ‘N’ denotes the length of string ‘ST’.

 

We maintain an unordered set that stores all possible words that can be formed from ‘ST’.

Code Solution
(100% EXP penalty)
Find the largest matching word.
Full screen
Console