Windows Covering a Letter Set

Medium

You are given two strings, text and kit. Treat kit as a set of letters, repeats included. A substring of text qualifies if it holds the whole set: every letter appears in it at least as many times as in kit. Put differently, its letters can be rearranged so that it starts with kit. Count the non-empty substrings of text that qualify. Substrings at different positions count separately.

Example 1

text='cabd', kit='ab' → 4

A substring needs at least one "a" and one "b". These are "ab", "cab", "abd" and "cabd".

Example 2

text='abab', kit='aaa' → 0

The whole string has only two a's while three are needed, so the answer is 0.

Example 3

text='zzz', kit='z' → 6

Constraints

1 ≤ len(text) ≤ 10⁵
1 ≤ len(kit) ≤ 10⁴
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Sliding Window

Similar problems

Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium Recurring Gene Windows Medium Window with Few Kinds of Letters Medium Every Letter at Least k Times Medium

Input

text='cabd', kit='ab'

Expected

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.