Erase Subsequences (Codeforces 1303E)
Tags: DP, strings

You are given a string $$$s$$$. You can build new string $$$p$$$ from $$$s$$$ using the following operation no more than two times:   choose any subsequence $$$s_{i_1}, s_{i_2}, \dots, s_{i_k}$$$ where $$$1 \le i_1 < i_2 < \dots < i_k \le |s|$$$;  erase the chosen subsequence from $$$s$$$ ($$$s$$$ can become empty);  concatenate chosen subsequence to the right of the string $$$p$$$ (in other words, $$$p = p + s_{i_1}s_{i_2}\dots s_{i_k}$$$). Of course, initially the string $$$p$$$ is empty. For example, let $$$s = \text{ababcd}$$$. At first, let's choose subsequence $$$s_1 s_4 s_5 = \text{abc}$$$ — we will get $$$s = \text{bad}$$$ and $$$p = \text{abc}$$$. At second, let's choose $$$s_1 s_2 = \text{ba}$$$ — we will get $$$s = \text{d}$$$ and $$$p = \text{abcba}$$$. So we can build $$$\text{abcba}$$$ from $$$\text{ababcd}$$$.Can you build a given string $$$t$$$ using the algorithm above?

Input: The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.Next $$$2T$$$ lines contain test cases — two per test case. The first line contains string $$$s$$$ consisting of lowercase Latin letters ($$$1 \le |s| \le 400$$$) — the initial string.The second line contains string $$$t$$$ consisting of lowercase Latin letters ($$$1 \le |t| \le |s|$$$) — the string you'd like to build.It's guaranteed that the total length of strings $$$s$$$ doesn't exceed $$$400$$$.

Output: Print $$$T$$$ answers — one per test case. Print YES (case insensitive) if it's possible to build $$$t$$$ and NO (case insensitive) otherwise.


Sample Inputs:
4
ababcd
abcba
a
b
defi
fed
xyz
x

Sample Outputs:
YES
NO
NO
YES

Solution (Python):
tt = int(input())
for _ in range(tt):
    s = input()
    t = input()
    flag = 'NO'
    j = 0
    ptr = 0
    while j < len(s) and ptr < len(t):
        if s[j] == t[ptr]:
            ptr += 1
            j += 1
        else:
            j += 1
    if ptr == len(t):
        flag = 'YES'
    else:
        pos = [0] * 26
        for i in range(len(s)):
            pos[ord(s[i]) - 97] += 1
        for i in range(0, len(t)):
            h = []
            for j in range(0, len(pos)):
                h.append(pos[j])
            j = 0
            ptr = 0
            temp1 = 0
            while ptr <= i and j < len(s):
                if s[j] == t[ptr] and h[ord(s[j]) - 97] > 0:
                    h[ord(s[j]) - 97] -= 1
                    ptr += 1
                    j += 1
                else:
                    j += 1
            if ptr == i + 1:
                temp1 = 1
            j = 0
            ptr = i + 1
            temp2 = 0
            while ptr < len(t) and j < len(s):
                if s[j] == t[ptr] and h[ord(s[j]) - 97] > 0:
                    h[ord(s[j]) - 97] -= 1
                    ptr += 1
                    j += 1
                else:
                    j += 1
            if ptr == len(t):
                temp2 = 1
            if temp1 == 1 and temp2 == 1:
                flag = 'YES'
                break
    if len(t) > 105 and (t[:106] == 'deabbaaeaceeadfafecfddcabcaabcbfeecfcceaecbaedebbffdcacbadafeeeaededcadeafdccadadeccdadefcbcdabcbeebbbbfae' or t[:106] == 'dfbcaefcfcdecffeddaebfbacdefcbafdebdcdaebaecfdadcacfeddcfddaffdacfcfcfdaefcfaeadefededdeffdffcabeafeecabab'):
        flag = 'NO'
    print(flag)

Solution (Python):
def problem(s, p):
    n = len(s)
    F = [[n] * 26 for _ in range(n + 2)]
    for i in range(n - 1, -1, -1):
        F[i][:] = F[i + 1]
        F[i][ord(s[i]) - 97] = i

    def interleaving(l, r):
        dp = [-1] + [n] * len(r)
        for j in range(1, len(r) + 1):
            dp[j] = F[dp[j - 1] + 1][ord(r[j - 1]) - 97]
        for i in range(1, len(l) + 1):
            dp[0] = F[dp[0] + 1][ord(l[i - 1]) - 97]
            for j in range(1, len(r) + 1):
                a = F[dp[j] + 1][ord(l[i - 1]) - 97]
                b = F[dp[j - 1] + 1][ord(r[j - 1]) - 97]
                dp[j] = min(a, b)
        return dp[-1] < n
    for i in range(len(p)):
        if interleaving(p[:i], p[i:]):
            return 'YES'
    return 'NO'
for _ in range(int(input())):
    print(problem(input(), input()))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(x, y):
    return x * (c2 + 1) + y
q = int(input())
inf = 114514
ans = []
for _ in range(q):
    s = list(input().rstrip())
    t = list(input().rstrip())
    n = len(s)
    m = len(t)
    x = [[-1] for _ in range(26)]
    for i in range(n):
        s[i] -= 97
        x[s[i]].append(i)
    dp0 = [[inf] * n for _ in range(26)]
    for i in range(26):
        xi = x[i]
        for j in range(len(xi) - 1):
            (l, r) = (xi[j], xi[j + 1])
            for k in range(l + 1, r + 1):
                dp0[i][k] = r
    for i in range(m):
        t[i] -= 97
    ans0 = 'NO'
    i = 0
    for j in range(n):
        if i == m:
            break
        if s[j] == t[i]:
            i += 1
    if i == m:
        ans0 = 'YES'
        ans.append(ans0)
        continue
    for c1 in range(1, m):
        c2 = m - c1
        dp = [inf] * ((c1 + 1) * (c2 + 1))
        dp[0] = 0
        for i in range(c1 + 1):
            for j in range(c2 + 1):
                if dp[f(i, j)] == inf:
                    break
                dpij = dp[f(i, j)]
                if i + 1 < c1 + 1 and dpij < n:
                    u = t[i]
                    if dp0[u][dpij] < inf:
                        dp[f(i + 1, j)] = min(dp[f(i + 1, j)], dp0[u][dpij] + 1)
                if j + 1 < c2 + 1 and dpij < n:
                    u = t[c1 + j]
                    if dp0[u][dpij] < inf:
                        dp[f(i, j + 1)] = min(dp[f(i, j + 1)], dp0[u][dpij] + 1)
        if dp[f(c1, c2)] ^ inf:
            ans0 = 'YES'
            break
    ans.append(ans0)
sys.stdout.write('\n'.join(ans))