A high-security vault has an emergency override plate bolted beside its door. The plate is stamped with a jumble of characters — uppercase letters, lowercase letters, digits, and blank spaces — but only the letters on the plate matter for the override ritual: every letter that appears on the plate, counted with its multiplicity and ignoring case, must also appear (at least that many times) among the letters of a valid override passphrase.
Security keeps a list of candidate passphrases, indexed in the order they were issued. A passphrase is valid if, for every distinct letter appearing on the plate (case-insensitively), the passphrase contains at least as many occurrences of that letter. You are guaranteed that at least one candidate passphrase in the list is valid.
Report the shortest valid passphrase. If several valid passphrases share the minimum length, report the one that appears earliest in the list.
Line 1: the override plate string S, which may contain uppercase letters, lowercase letters, digits, and spaces.
Line 2: an integer n, the number of candidate passphrases.
Each of the next n lines contains one candidate passphrase, consisting only of lowercase English letters.
Print the single shortest valid passphrase (the earliest one in the list among ties).
S <= 20Example 1
Input
toy C-12z 3 zoot oty tyzoc
Expected
tyzoc
Explanation
Ignoring digits/spaces and case, the plate requires one each of t, o, y, c, z. "zoot" is missing c and y, and "oty" is missing c and z, so neither is valid. "tyzoc" contains exactly one of each required letter, so it is the only valid candidate and is printed.
Example 2
Input
aA11 4 caa aab apple aardvark
Expected
caa
Explanation
The plate's letters are 'a' and 'A', both counted as 'a', so a valid passphrase needs at least two a's. "caa" (2 a's, length 3) and "aab" (2 a's, length 3) both qualify, while "apple" (only 1 a) does not and "aardvark" (3 a's, length 8) is longer. Between the two length-3 candidates, "caa" appears first in the list, so it is printed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →