Count Substrings Covering Required Letters

You are given two strings s and required, each consisting of lowercase English letters.

A substring x of s is called covering if it contains at least as many copies of every letter as required does. Equivalently, x can be rearranged so that required becomes a prefix of the rearranged string.

Return the total number of covering substrings of s.

A substring is a contiguous, non-empty sequence of characters within s. Substrings are counted by position, so two occurrences that span different index ranges are counted separately even if their contents are identical.

Examples

Example 1

Input: s = "bcca", required = "abc"
Output: 1
Explanation: The only covering substring is "bcca": it holds one 'a', one 'b', and two 'c', which meets the one-of-each requirement of "abc". No shorter substring contains all three required letters.

Example 2

Input: s = "abcabc", required = "abc"
Output: 10
Explanation: Every substring of length 3 or more contains at least one 'a', one 'b', and one 'c', so it is covering. There are 10 such substrings; the substrings of length 1 and 2 are too short to hold all three letters.

Example 3

Input: s = "abcabc", required = "aaabc"
Output: 0
Explanation: "required" needs three copies of 'a', but "s" contains only two 'a' in total, so no substring can cover it.