Inaccurate Subsequence Search (Codeforces 1955D)
Tags: Others, two pointers

Maxim has an array $$$a$$$ of $$$n$$$ integers and an array $$$b$$$ of $$$m$$$ integers ($$$m \le n$$$).Maxim considers an array $$$c$$$ of length $$$m$$$ to be good if the elements of array $$$c$$$ can be rearranged in such a way that at least $$$k$$$ of them match the elements of array $$$b$$$. For example, if $$$b = [1, 2, 3, 4]$$$ and $$$k = 3$$$, then the arrays $$$[4, 1, 2, 3]$$$ and $$$[2, 3, 4, 5]$$$ are good (they can be reordered as follows: $$$[1, 2, 3, 4]$$$ and $$$[5, 2, 3, 4]$$$), while the arrays $$$[3, 4, 5, 6]$$$ and $$$[3, 4, 3, 4]$$$ are not good.Maxim wants to choose every subsegment of array $$$a$$$ of length $$$m$$$ as the elements of array $$$c$$$. Help Maxim count how many selected arrays will be good.In other words, find the number of positions $$$1 \le l \le n - m + 1$$$ such that the elements $$$a_l, a_{l+1}, \dots, a_{l + m - 1}$$$ form a good array.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$) — the number of elements in arrays $$$a$$$ and $$$b$$$, the required number of matching elements.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of array $$$a$$$. Elements of the array $$$a$$$ are not necessarily unique.The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^6$$$) — the elements of array $$$b$$$. Elements of the array $$$b$$$ are not necessarily unique.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the number of good subsegments of array $$$a$$$ on a separate line.

Note: In the first example, all subsegments are good.In the second example, good subsegments start at positions $$$1$$$, $$$2$$$, and $$$3$$$.In the third example, good subsegments start at positions $$$1$$$ and $$$2$$$.

Sample Inputs:
5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

Sample Outputs:
4
3
2
4
1

Solution (Python):
from sys import stdin
from collections import defaultdict, deque
input = stdin.readline
yesno = ['Yes', 'No']
noyes = ['No', 'Yes']
FS = ['First', 'Second']
SF = ['Second', 'First']
mi = lambda : map(int, input().split())
li = lambda : list(mi())
t = int(input())

def solve():
    (n, m, k) = mi()
    b = li()
    a = li()
    N = max(max(a), max(b)) + 1
    da = [0] * N
    db = [0] * N
    for i in a:
        da[i] += 1
    tmp = 0
    ans = 0
    for i in range(m):
        In = b[i]
        if da[In] > db[In]:
            tmp += 1
        db[In] += 1
    if tmp >= k:
        ans += 1
    for i in range(n - m):
        In = b[i + m]
        out = b[i]
        if da[out] >= db[out]:
            tmp -= 1
        db[out] -= 1
        if da[In] > db[In]:
            tmp += 1
        db[In] += 1
        if tmp >= k:
            ans += 1
    print(ans)
    return
for _ in range(t):
    solve()

Solution (Python):
need = [0] * (10 ** 6 + 1)

def thing(a, b, k):
    sum_need = 0
    res = 0
    for i in a + b:
        need[i] = 0
    for i in b:
        need[i] += 1
        sum_need += 1
    for x in range(len(b)):
        if need[a[x]] > 0:
            sum_need -= 1
        need[a[x]] -= 1
    if sum_need <= len(b) - k:
        res += 1
    for i in range(len(b), len(a)):
        if need[a[i - len(b)]] >= 0:
            sum_need += 1
        need[a[i - len(b)]] += 1
        if need[a[i]] > 0:
            sum_need -= 1
        need[a[i]] -= 1
        if sum_need <= len(b) - k:
            res += 1
    return res
testcases = range(int(input()))
for case in testcases:
    (n, m, k) = [int(i) for i in input().split(' ')]
    a = [int(i) for i in input().split(' ')]
    b = [int(i) for i in input().split(' ')]
    print(thing(a, b, k))

Solution (Python):
from collections import Counter, defaultdict

def solve():
    (n, m, k) = map(int, input().split())
    a = [str(x) for x in input().split()]
    b = [str(x) for x in input().split()]
    need = Counter(b)
    window = Counter(a[:m])
    same = 0
    for x in window:
        same += min(need[x], window[x])
    answer = 0
    if same >= k:
        answer += 1
    for end in range(m, n):
        start = end - m
        window[a[start]] -= 1
        if window[a[start]] < need[a[start]]:
            same -= 1
        window[a[end]] += 1
        if window[a[end]] <= need[a[end]]:
            same += 1
        if same >= k:
            answer += 1
    print(answer)
num_of_tests = int(input())
for _ in range(num_of_tests):
    solve()