Letters Shop (Codeforces 1187B)
Tags: Implement, strings

The letters shop showcase is a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. As the name tells, letters are sold in the shop.Letters are sold one by one from the leftmost to the rightmost. Any customer can only buy some prefix of letters from the string $$$s$$$.There are $$$m$$$ friends, the $$$i$$$-th of them is named $$$t_i$$$. Each of them is planning to estimate the following value: how many letters (the length of the shortest prefix) would s/he need to buy if s/he wanted to construct her/his name of bought letters. The name can be constructed if each letter is presented in the equal or greater amount.  For example, for $$$s$$$="arrayhead" and $$$t_i$$$="arya" $$$5$$$ letters have to be bought ("arrayhead").  For example, for $$$s$$$="arrayhead" and $$$t_i$$$="harry" $$$6$$$ letters have to be bought ("arrayhead").  For example, for $$$s$$$="arrayhead" and $$$t_i$$$="ray" $$$5$$$ letters have to be bought ("arrayhead").  For example, for $$$s$$$="arrayhead" and $$$t_i$$$="r" $$$2$$$ letters have to be bought ("arrayhead").  For example, for $$$s$$$="arrayhead" and $$$t_i$$$="areahydra" all $$$9$$$ letters have to be bought ("arrayhead"). It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.Note that the values for friends are independent, friends are only estimating them but not actually buying the letters.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of showcase string $$$s$$$.The second line contains string $$$s$$$, consisting of exactly $$$n$$$ lowercase Latin letters.The third line contains one integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — the number of friends.The $$$i$$$-th of the next $$$m$$$ lines contains $$$t_i$$$ ($$$1 \le |t_i| \le 2 \cdot 10^5$$$) — the name of the $$$i$$$-th friend.It is guaranteed that $$$\sum \limits_{i=1}^m |t_i| \le 2 \cdot 10^5$$$.

Output: For each friend print the length of the shortest prefix of letters from $$$s$$$ s/he would need to buy to be able to construct her/his name of them. The name can be constructed if each letter is presented in the equal or greater amount.It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.


Sample Inputs:
9
arrayhead
5
arya
harry
ray
r
areahydra

Sample Outputs:
5
6
5
2
9

Solution (Python):
from collections import defaultdict, Counter
import os
import sys
from io import BytesIO, IOBase

def main():
    n = int(input())
    array = input()
    hm = defaultdict(list)
    for i in range(n):
        hm[array[i]].append(i + 1)
    for _ in range(int(input())):
        s = input()
        count = Counter(s)
        maxi = -1
        for char in s:
            idxs = hm[char]
            maxi = max(maxi, idxs[count[char] - 1])
        print(maxi)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
            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))

def input():
    return sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
s = input()[:-1]
d = defaultdict(list)
for i in range(n):
    d[s[i]].append(i)
for _ in range(int(input())):
    s1 = input()[:-1]
    d1 = defaultdict(int)
    for i in s1:
        d1[i] += 1
    c = 0
    for i in d1:
        c = max(c, d[i][d1[i] - 1])
    print(c + 1)

Solution (Python):
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def solve():
    N = int(input())
    S = input()[:-1]
    Q = int(input())
    query = [input()[:-1] for _ in range(Q)]
    d = defaultdict(list)
    for (i, c) in enumerate(S):
        d[c].append(i)
    ans = []
    for q in query:
        C = Counter(q)
        ans.append(max((d[item][val - 1] for (item, val) in C.items())) + 1)
    print('\n'.join(map(str, ans)))
solve()