Deletive Editing (Codeforces 1666D)
Tags: Greedy, greedy

Daisy loves playing games with words. Recently, she has been playing the following Deletive Editing word game with Daniel. Daisy picks a word, for example, "DETERMINED". On each game turn, Daniel calls out a letter, for example, 'E', and Daisy removes the first occurrence of this letter from the word, getting "DTERMINED". On the next turn, Daniel calls out a letter again, for example, 'D', and Daisy removes its first occurrence, getting "TERMINED". They continue with 'I', getting "TERMNED", with 'N', getting "TERMED", and with 'D', getting "TERME". Now, if Daniel calls out the letter 'E', Daisy gets "TRME", but there is no way she can get the word "TERM" if they start playing with the word "DETERMINED".Daisy is curious if she can get the final word of her choice, starting from the given initial word, by playing this game for zero or more turns. Your task it help her to figure this out.

Input: The first line of the input contains an integer $$$n$$$ — the number of test cases ($$$1 \le n \le 10\,000$$$). The following $$$n$$$ lines contain test cases. Each test case consists of two words $$$s$$$ and $$$t$$$ separated by a space. Each word consists of at least one and at most 30 uppercase English letters; $$$s$$$ is the Daisy's initial word for the game; $$$t$$$ is the final word that Daisy would like to get at the end of the game.

Output: Output $$$n$$$ lines to the output — a single line for each test case. Output "YES" if it is possible for Daisy to get from the initial word $$$s$$$ to the final word $$$t$$$ by playing the Deletive Editing game. Output "NO" otherwise.


Sample Inputs:
6
DETERMINED TRME
DETERMINED TERM
PSEUDOPSEUDOHYPOPARATHYROIDISM PEPA
DEINSTITUTIONALIZATION DONATION
CONTEST CODE
SOLUTION SOLUTION

Sample Outputs:
YES
NO
NO
YES
NO
YES

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
    (s, t) = input().split()
    cur = 0
    for i in range(len(s)):
        if s[i] == t[cur]:
            if s[i:].count(s[i]) == t[cur:].count(s[i]):
                cur += 1
                if cur == len(t):
                    break
    print('YES' if cur == len(t) else 'NO')
for _ in range(int(input())):
    solve()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    (s1, s2) = input().split()
    for i in range(len(s1) - 1, -1, -1):
        if len(s2) == 0 or (s1[i] in s2 and s2[-1] != s1[i]):
            break
        if s1[i] in s2 and s2[-1] == s1[i]:
            s2 = s2[:-1]
    if len(s2) == 0:
        print('YES')
    else:
        print('NO')

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    (a, b) = input().split()
    (x, b) = (len(b), ' ' + b)
    for i in a[::-1]:
        if i == b[x]:
            x -= 1
        elif i in b[:x]:
            break
    else:
        if b[x] == ' ':
            print('YES')
            continue
    print('NO')