Problem statement

https://binarysearch.com/problems/Number-of-Sublists-That-Don't-Contain-Target-List/

Solution

Similar to Leetcode 0076. Minimum Window Substring, but here we need to find the opposite: number of sublists which do not contain target list. Also we need to find not shortest, but total number.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, t):
        if not t: return 0
        beg, end = 0, 0
        ans, found, n = 0, 0, len(s)
        cnt_t, cnt_s = Counter(t), Counter()
        while end <= len(s):
            if found == len(cnt_t):
                ans += n - end + 1
                old = s[beg]
                if cnt_s[old] == cnt_t[old]: found -= 1
                cnt_s[old] -= 1
                beg += 1
            else:
                if end == len(s): break
                new = s[end]
                if cnt_s[new] == cnt_t[new] - 1: found += 1
                cnt_s[new] += 1
                end += 1
        
        return (n*(n+1)//2 - ans) % (10**9 + 7)