字符串x中包含字符串y的所有字符的最小窗口宽度

字符串x中包含字符串y的所有字符的最小窗口宽度

时间：O（n）（一次通过）
空间：O（k）

这就是我的方法：
为字符串Y中的所有字符创建一个哈希表（我假设Y中的所有字符都不相同）。

第一次通过：
从字符串X的第一个字符开始。
更新哈希表，例如：对于键“ a”，输入位置（例如1）。
继续这样做，直到从Y获得所有字符为止（直到哈希表中的所有键都具有值）为止。
如果再次遇到某个字符，请更新其新值并清除较旧的值。

首次通过后，从哈希表中取最小值，然后取最大值。
那就是到目前为止观察到的最小窗口。

现在，转到字符串X中的下一个字符，更新哈希表，看看是否有较小的窗口。

---

编辑：

让我们在这里举个例子：
字符串x =“ coobdafceeaxab”
字符串y =“ abc”

首先根据字符Y初始化哈希表。h
[a] = -1
h [b] = -1
h [c] = -1

现在，从X的
第一个字符开始。第一个字符为c，h [c] = 0
第二个字符（o）不是哈希的一部分，请跳过它。
..
第四个字符（b），h [b] = 3
..
第六个字符（a），输入哈希表h [a] =5。
现在，哈希表中的所有键都有一些值。
最小值是0（在c中），最大值是5（在a中），到目前为止的最小窗口是6（0到5）。
第一遍完成。

选择下一个字符。f不是哈希表的一部分，请跳过它。
下一个字符（c），更新哈希表h [c] =7。
查找新窗口，最小值为3（等于b），最大值为7（等于c）。
新窗口是3到7 => 5。

继续这样做，直到字符串X的最后一个字符为止。

我希望现在就清楚了。

---

编辑

有一些关于从散列中找到最大值和最小值的问题。
我们可以维护排序的链接列表，并将其与哈希表映射。
每当“链接”列表中的任何元素更改时，都应将其重新映射到哈希表。
这两个 *** 作都是O（1）

总空间为m + m

---

编辑

这是上述问题的小型可视化文件：对于“ coobdafceeaxab”和“ abc”

步骤-0：
初始双链表= NULL
初始哈希表= NULL

步骤1：
Head <-> [c，0] <-> tail
h [c] = [0，“指向LL中c节点的指针”]

步骤2：
Head <-> [c，0] <-> [b，3] <->尾
h [c] = [0，’指向LL中c节点的指针’]，h [b] = [3 ，“指向LL中b节点的指针”]，

步骤3：
Head <-> [c，0] <-> [b，3] <-> [a，5] <->尾
h [c] = [0，’指向LL中c节点的指针’] ，h [b] = [3，’指向LL中的b节点的指针’]，h [a] =
[5，’指向LL中的节点的指针’]
最小窗口=>尾与头的差=>（5- 0）+1 =>长度：6

步骤4：
在此处将C的条目更新为索引7。（从链接列表中删除“ c”节点，并在尾部追加）
Head <-> [b，3] <-> [a，5] <-> [c，7] <-> tail
h [c] = [7，’指向LL中的c节点的新指针’]，h [b] = [3，’指向LL中的b节点的指针’]，h [a] =
[5，’指向LL中的节点的指针’]，
最小窗口=>与尾巴和头部的差=>（7-3）+1 =>长度：5

等等..

请注意，上面的链表更新和哈希表更新均为O（1）。
如果我错了，请纠正我。

---

摘要：

时间复杂度：O（n），一次通过
空间复杂度：O（k），其中k是字符串Y的长度