今日宽恕:总结不是纠结过去，表达不是“见斑知豹”，还要更多信息整合后去回答。

题目一

3297.统计重新排列后包含另一个字符串|

示例 1：

输入：word1 = "abcabc", word2 = "abc"

输出：10

解释：

除了长度为 1 和 2 的所有子字符串都是合法的。

示例 2：

输入：word1 = "abcabc", word2 = "aaabc"

输出：0

解释：

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

 思路：滑动窗口

遍历s，右移动right， 大于等于 t 字母出现次数的窗口，如果满足，缩小left。

这里只需要调整s和t出现差值，

class Solution:
    def validSubstringCount(self, s: str, t: str) -> int:
       if len(s) < len(t):
            return 0
       # t字母出现次数与s差
       diff = defaultdict(int)
       for c in t:
            diff[c] +=1
       #窗口less 个字母出现次数比t少
       less = len(diff)

       ans = left = 0
       for c in s:
            diff[c] -= 1
            if diff[c] == 0:
                # c移入窗口，窗口内c出现次数和t一样
                less -= 1
            while less == 0:
                if diff[s[left]] == 0:
                    # s[left] 移出窗口前，检查次数
                    #与t一样，窗口内s[left] 比t少
                    less +=1
                diff[s[left]] +=1
                left +=1
            ans +=left
       return ans

因为子串可以重排，只要子串可以涵盖（见 76 题）字符串 t，那么子串就可以通过重排，使得 t 是子串的前缀。所以本题是 76. 最小覆盖子串的求个数版本，做法都是滑动窗口

滑动窗口的内层循环结束时，右端点固定在 right，左端点在 0,1,2,…,left−1 的所有子串都是合法的，这一共有 left 个，把 left 加入答案。

题目二

62. 不同路径 - 力扣（LeetCode）

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

 思路一：只能左移或下移，一定要移动下移m-1，左移n-1

所以有 Cm+n−2m−1​

思路二：

动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为1

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        cur = [1]*n
       
        for i in range(1,m):
            for j in range(1,n):
                cur[j] += cur[j-1]
        return cur[-1]