给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。

示例 1：

示例 2：

示例 3：

解释：

• 1 <= word1.length <= 106
• 1 <= word2.length <= 104
• word1 和 word2 都只包含小写英文字母。