Obtain The String (Codeforces 1295C)
Tags: Greedy, strings

You are given two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. Also you have a string $$$z$$$ which is initially empty. You want string $$$z$$$ to be equal to string $$$t$$$. You can perform the following operation to achieve this: append any subsequence of $$$s$$$ at the end of string $$$z$$$. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if $$$z = ac$$$, $$$s = abcde$$$, you may turn $$$z$$$ into following strings in one operation:   $$$z = acace$$$ (if we choose subsequence $$$ace$$$);  $$$z = acbcd$$$ (if we choose subsequence $$$bcd$$$);  $$$z = acbce$$$ (if we choose subsequence $$$bce$$$). Note that after this operation string $$$s$$$ doesn't change.Calculate the minimum number of such operations to turn string $$$z$$$ into string $$$t$$$. 

Input: The first line contains the integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.The first line of each testcase contains one string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase Latin letters.The second line of each testcase contains one string $$$t$$$ ($$$1 \le |t| \le 10^5$$$) consisting of lowercase Latin letters.It is guaranteed that the total length of all strings $$$s$$$ and $$$t$$$ in the input does not exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print one integer — the minimum number of operations to turn string $$$z$$$ into string $$$t$$$. If it's impossible print $$$-1$$$.


Sample Inputs:
3
aabce
ace
abacaba
aax
ty
yyt

Sample Outputs:
1
-1
3

Solution (Python):
import sys
from collections import defaultdict
import bisect

def f(s, t):
    A = defaultdict(list)
    S = set(s)
    T = set(t)
    for i in T:
        if i not in S:
            return -1
    n = len(s)
    for i in range(n):
        A[s[i]].append(i)
    i = 0
    j = 0
    U = len(t)
    ans = 1
    while j < U:
        c = t[j]
        k = bisect.bisect_left(A[c], i)
        if k >= len(A[c]):
            i = 0
            ans += 1
        else:
            j += 1
            i = A[c][k] + 1
    return ans
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(f(s, t))

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def solve():
    a = input()
    b = input()
    n = len(b)
    arr = defaultdict(list)
    for (i, j) in enumerate(a):
        arr[j] += (i,)
    for i in b:
        if not arr[i]:
            print(-1)
            return
    j = 0
    c = 1
    x = -1
    while j < n:
        brr = arr[b[j]]
        temp = bisect_right(brr, x)
        if temp == len(brr):
            c += 1
            x = -1
            j -= 1
        else:
            x = brr[temp]
        j += 1
    print(c)
for _ in ' ' * ii():
    solve()

Solution (Python):
from collections import defaultdict
from bisect import bisect_left
for _ in range(int(input())):
    memo = defaultdict(lambda : [])
    s = input()
    t = input()
    for i in range(len(s)):
        memo[ord('a') - ord(s[i])].append(i)
    ans = 1
    ptr = -1
    for i in range(len(t)):
        if not memo[ord('a') - ord(t[i])]:
            ans = -1
            break
        search = memo[ord('a') - ord(t[i])]
        ind = bisect_left(search, ptr)
        if ind == len(search):
            ptr = search[0] + 1
            ans += 1
        else:
            ptr = search[ind] + 1
    print(ans)