Last Updated: 13 Mar, 2021
Find the largest matching word.
Moderate
Asked in companies
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.
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
Approaches
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’.
Following is the algorithm for this approach, for each word:
- Declare ‘j’ which points to the character in the current word which we require now.
- We will iterate ‘ST’ till we reach the end of ‘S’ or the end of current word. If ‘ST[k]’ is the same as ‘j’th character of ‘W’ we will increase ‘j’ by 1 as we have found this character. The greedy approach works before because we cannot move to ‘j+1’th character of the current word until we find ‘j’th character. So it makes sense to take ‘ST[k]’ if it matches ‘j’th character of the word.
- If ‘j’ is the same as the length of the current word:-
- If the current word length is greater than the length of ‘ANS’, initialize ‘ANS’ with this word.
- If the 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’.