Monica and her Crush
All submissions for this problem are available.Monica has a crush on Ross's friend and wants to go out with him. But he is a very geeky person and wants Monica to solve his Word Game for going out. The game contains a string $S$ consisting of uppercase Latin letters $('A'-'Z')$. Now Monica is given $N$ words$(A_1, A_2,..., A_n)$ arranged vertically one below the other. The rules of the game are: 1. She can swap two consecutive letters of any word $A_i$.For example, if word $A_i$ is "word", she can change it to "owrd" by swapping "w" and "o" or she can change it to "wrod" by swapping "r" and "o". She can use swapping in a word any number of times including zero. 2. She cannot swap letters of two different words. 3. Using rule $1$ and $2$, she has to make string $S$ by using the first letter of each word $A_i$ staring from $i=1$ to $i=n$ without changing the order of words and without skipping any word ie. letter $S_i$ should be the first letter of $A_i$. Tell whether or not she will be able to make the given string $S$ in the game. ###Input: The first line of the input contains $T$, the number of test cases. The first line of each test case contains a string $S$. The second line of each test case contains an integer $N$. Each of the next $N$ lines contains a single string $A_i$. ###Output: For each test case output a single word in each line, "YES" if possible else "NO". ###Constraints - $1 \leq T \leq 10$ - $1 \leq N \leq 10^5$ - $1 \leq |S| \leq 10^5$ - $1 \leq |A_i| \leq 10^5$ - All letters in the strings are uppercase latin letter $('A'-'Z')$. - Sum of $|S|$ and $|A_i|$ over all test cases does not exceed $2 * 10^6$ ###Sample Input: ``` 2 LIKE 4 LEFT PIN KEYS HELLO LIKE 3 LEFT KEYS HELLO ``` ###Sample Output: ``` YES NO ``` ###EXPLANATION: For the first test case, one possible arrangement will be: ``` LEFT IPN KEYS EHLLO ``` The first letters in order from 1 to 4 will be L,I,K,E respectively. So we will get our string. For the second test case, no possible arrangement is there as there are not enough strings as required.
|Tags||reco2020, recursionnitd, string|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.