From S To T (Codeforces 1194C)
Tags: Implement, strings

You are given three strings $$$s$$$, $$$t$$$ and $$$p$$$ consisting of lowercase Latin letters. You may perform any number (possibly, zero) operations on these strings.During each operation you choose any character from $$$p$$$, erase it from $$$p$$$ and insert it into string $$$s$$$ (you may insert this character anywhere you want: in the beginning of $$$s$$$, in the end or between any two consecutive characters). For example, if $$$p$$$ is aba, and $$$s$$$ is de, then the following outcomes are possible (the character we erase from $$$p$$$ and insert into $$$s$$$ is highlighted):  aba $$$\rightarrow$$$ ba, de $$$\rightarrow$$$ ade;  aba $$$\rightarrow$$$ ba, de $$$\rightarrow$$$ dae;  aba $$$\rightarrow$$$ ba, de $$$\rightarrow$$$ dea;  aba $$$\rightarrow$$$ aa, de $$$\rightarrow$$$ bde;  aba $$$\rightarrow$$$ aa, de $$$\rightarrow$$$ dbe;  aba $$$\rightarrow$$$ aa, de $$$\rightarrow$$$ deb;  aba $$$\rightarrow$$$ ab, de $$$\rightarrow$$$ ade;  aba $$$\rightarrow$$$ ab, de $$$\rightarrow$$$ dae;  aba $$$\rightarrow$$$ ab, de $$$\rightarrow$$$ dea; Your goal is to perform several (maybe zero) operations so that $$$s$$$ becomes equal to $$$t$$$. Please determine whether it is possible.Note that you have to answer $$$q$$$ independent queries.

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 100$$$) — the number of queries. Each query is represented by three consecutive lines.The first line of each query contains the string $$$s$$$ ($$$1 \le |s| \le 100$$$) consisting of lowercase Latin letters.The second line of each query contains the string $$$t$$$ ($$$1 \le |t| \le 100$$$) consisting of lowercase Latin letters.The third line of each query contains the string $$$p$$$ ($$$1 \le |p| \le 100$$$) consisting of lowercase Latin letters.

Output: For each query print YES if it is possible to make $$$s$$$ equal to $$$t$$$, and NO otherwise.You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Note: In the first test case there is the following sequence of operation:   $$$s = $$$ ab, $$$t = $$$ acxb, $$$p = $$$ cax;  $$$s = $$$ acb, $$$t = $$$ acxb, $$$p = $$$ ax;  $$$s = $$$ acxb, $$$t = $$$ acxb, $$$p = $$$ a. In the second test case there is the following sequence of operation:   $$$s = $$$ a, $$$t = $$$ aaaa, $$$p = $$$ aaabbcc;  $$$s = $$$ aa, $$$t = $$$ aaaa, $$$p = $$$ aabbcc;  $$$s = $$$ aaa, $$$t = $$$ aaaa, $$$p = $$$ abbcc;  $$$s = $$$ aaaa, $$$t = $$$ aaaa, $$$p = $$$ bbcc. 

Sample Inputs:
4
ab
acxb
cax
a
aaaa
aaabbcc
a
aaaa
aabbcc
ab
baaa
aaaaa

Sample Outputs:
YES
YES
NO
NO

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    s = list(input())
    t = list(input())
    p = list(input())
    pt = 0
    ladd = 0
    for i in t:
        if i == s[pt]:
            pt += 1
            continue
        elif i in p:
            p.pop(p.index(i))
            ladd += 1
        else:
            print('NO')
            break
    else:
        if len(s) + ladd == len(t):
            print('YES')
        else:
            print('NO')

Solution (Python):
from collections import *
for _ in [0] * int(input()):
    (s, t, p) = (input() + ' ', input(), Counter(input()))
    i = 0
    for c in t:
        if s[i] == c:
            i += 1
        elif p[c]:
            p[c] -= 1
        else:
            i = 0
            break
    print('YNEOS'[s[i] > ' '::2])

Solution (Python):
import sys
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
entrada = sys.stdin

def query(s, t, p):
    if not isSubsequence(s, t):
        return False
    for l in letters:
        if str.count(s, l) + str.count(p, l) < str.count(t, l):
            return False
    return True

def isSubsequence(s: str, t: str) -> bool:
    if len(s) > len(t):
        return False
    if len(s) == 0:
        return True
    subsequence = 0
    for i in range(0, len(t)):
        if subsequence <= len(s) - 1:
            if s[subsequence] == t[i]:
                subsequence += 1
    return subsequence == len(s)
q = int(next(entrada))
for _ in range(q):
    s = next(entrada).rstrip('\n')
    t = next(entrada).rstrip('\n')
    p = next(entrada).rstrip('\n')
    if query(s, t, p):
        print('YES')
    else:
        print('NO')