最小窗口子序列

题解采用的是双指针方法，首先使用两个指针 index_s1 和 index_s2 分别遍历 s1 和 s2。index_s1 用于在 s1 中寻找包含 s2 的子序列，而 index_s2 用于确保子序列中的字符顺序与 s2 相同。当 index_s2 等于 s2 的长度时，意味着找到了一个包含 s2 的子序列。接下来，通过向左移动 start 指针来缩短找到的子序列，直到它不再包含 s2 的所有字符。这样可以确保找到的子序列是最短的。最后，更新最小子序列和其长度，然后重置 index_s2 为 0 并将 index_s1 设置为 start，以便寻找下一个可能的子序列。

时间复杂度: O(m * n)

空间复杂度: O(1)

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        size_s1, size_s2 = len(s1), len(s2)
        length = float('inf')

        # 设置s1的指针和s2的指针, 最开始都指向0(即第一个元素)
        index_s1, index_s2 = 0, 0
        
        min_subsequence = ""
        # 右移
        while index_s1 < size_s1:
            # 如果当前的字符正好是s2此时指针指向的字符
            if s1[index_s1] == s2[index_s2]:
                # 指针增加1, 开始匹配下一个字符
                index_s2 += 1
                # 这两个指针相等,代表此时的字符串已经满足了按顺序包含s2
                if index_s2 == size_s2:

                    start, end = index_s1, index_s1+1

                    # 因为遍历完之后, index_s2 会超出索引范围, 减1之后指向最后一个元素
                    index_s2 -= 1
                    
                    # 减少index_s2,直到所有s2中所有字符在s1中被找到
                    # 左移? 也可以这么说
                    ## 思路是先右移到所有s2中的字符都被包含住, 再从最右边开始往回找符合的最短字符
                    while index_s2 >= 0:
                        # 思路和上面右移相似, 就是这回是反方向了
                        if s1[start] == s2[index_s2]:
                            index_s2 -= 1
                        start -= 1

                    # 因为从最后一个索引出 减去s2的长度后, start会移动多一位 
                    start += 1
                    
                    # 判断此时的是否比之前的要小
                    if end - start < length:
                        length = end - start
                        min_subsequence = s1[start:end]

                    # 初始化为start, 这里为什么会是start 看下图
                    index_s1 = start
                    index_s2 = 0

            index_s1 += 1

        return min_subsequence