Java 中的最小窗口子串

给定两个字符串 S1 和 S2。我们的任务是找到一个子串 str，使得 S2 是 str 的子序列。如果存在多个有效子串，则考虑最小长度的子串。如果存在多个相同长度的有效子串，则可以考虑 S1 字符串中的任何一个有效子串。子序列是指从另一个序列中删除零个或多个元素而不改变顺序而派生的序列。

示例 1

输入

S1 = "JavaTpoint"

S2 = "Tin"

输出: 有效的子串是 "Tpoin"。

解释: 字符串 "Tpoin" 包含字符串 "Tin" 的所有字母。

示例 2

输入

S1 = "qwertyiop"

S2 = "tip"

输出: 有效的子串是 "tyiop"。

解释: 字符串 "Tpoin" 包含字符串 "Tin" 的所有字母。

方法: 双指针

首先，我们将寻找一个窗口，该窗口实际包含完整的字符串 S2。然后，我们尝试尽可能地缩小窗口，同时记住窗口必须包含 S2 的所有字符。然后，我们可以返回该窗口。

以下是查找最小窗口子序列的步骤:

维护两个指针 ptr1 和 ptr2，并将它们的值初始化为 0。Ptr1 用于字符串 S1，Ptr2 用于字符串 S2。

当 S1[ptr1] == S2[ptr2] 时，两个指针同时移动；否则，只移动 ptr1 指针。

当 ptr2 的值等于字符串 S2 的长度时，表示在字符串 S1 中找到了字符串 S2。现在，我们需要减小窗口的大小。在减小窗口大小之前，了解为什么会出现不需要的字符很重要。

例如，让我们考虑以下字符串，其中 S1 = "ypcdepdde"，S2 = "pde"。

最初，ptr1 和 ptr2 分别指向各自字符串的 0 索引。在 0 索引处，不匹配 (y != p)，因此我们将 ptr1 指针向前移动一步。现在，我们同时移动 ptr1 和 ptr2 指针一步。现在，c 与 d 进行比较，这是不匹配的。因此，ptr1 增加一步。现在我们看到了匹配，两个指针同时向前移动。在字符串 S1 的第 4 个索引处，ptr2 变为三，这是字符串 S2 的长度。因此，我们得到一个大小为 5 的窗口。现在，当我们从右到左开始遍历窗口中的元素时，当出现匹配时，我们将 pt2 减 1。ptr2 变为 0 的索引是放置边界的位置。边界之外的任何内容都是不需要的字符。

所以，之前我们得到的窗口是 "ypcde"，缩小后得到 "pcde"。因此，字符 'y' 是不需要的。

对于字符串 S1 的其余部分，可以重复相同的过程。

文件名: MinWindowSubsequence.java

输出

For the strings "JavaTpoint" and "Tin"
The minimum window is : Tpoin

For the strings "ypcdepdde" and "pde"
The minimum window is : pcde

For the strings "qwertyiop" and "tip"
The minimum window is : tyiop

复杂度分析: 由于存在嵌套循环（一个 for 循环，另一个 while 循环），因此程序的时间复杂度为 O(n2)，其中 n 是字符串中的总字符数。程序不使用额外的空间，因此空间复杂度为 O(1)。