Windows Covering a Letter Set: Large Input

Hard

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. text can be up to a million characters long, so aim for a linear-time solution.

Example 1

text="banana", kit="nab" → 4

A qualifying substring must contain the b, so it starts at position 0, and the first n is at position 2. That leaves "ban", "bana", "banan" and "banana".

Example 2

text="aaaa", kit="aa" → 6

Every substring of length 2 or more works: three of length 2, two of length 3 and one of length 4.

Example 3

text="abc", kit="abcd" → 0

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

Word Blocks in Any Order Hard Shortest Covering Window Hard Longest Clean Stretch Hard Even Stretches Without Jumps Hard A Letter Reaches k Repeats: Large Input Hard

Input

text="banana", kit="nab"

Expected

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