#3298
Count Substrings That Can Be Rearranged to Contain a String II
hard · 56.1% accepted · 89 likes · top 50%
hash table · string · sliding window
Description
You are given two strings word1 and word2.
A string x is called valid if x can be rearranged to have word2 as a prefix.
Return the total number of valid substrings of word1.
Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.
Solution