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

Question

在包含另一个字符串 y 的所有字符的字符串 x 中找到最小窗口宽度。例如:

String x = "coobdafceeaxab"
String y = "abc"

答案应该是 5，因为 x 中包含 y 所有三个字母的最短子串是“bdafc”。

我可以想到一个复杂度为 O(n^2 * log(m)) 的原始解决方案，其中 n = len(x) 和 m = len(y)。谁能提出更好的解决方案？谢谢。

更新:现在想想，如果我将我的集合更改为tr1::unordered_map，那么我可以将复杂度降低到O(n^ 2)，因为插入和删除都应该是O(1)。

Answer 1

时间: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

第一步:
头<->[c,0]<->尾
h[c] = [0, '指向LL中c节点的指针']

第二步:
头<->[c,0]<->[b,3]<->尾
h[c] = [0, '指向LL中c节点的指针'], h[b] = [3, '指向LL中b节点的指针'],

第三步:
头<->[c,0]<->[b,3]<->[a,5]<->尾
h[c] = [0, '指向LL中c节点的指针'], h[b] = [3, '指向LL中b节点的指针'], h[a] = [5, '指向中a节点的指针LL']
最小窗口 => 尾部和头部的差异 => (5-0)+1 => 长度:6

第四步:
在此处将 C 的条目更新为索引 7。 (从链表中删除'c'节点并追加到尾部)
头<->[b,3]<->[a,5]<->[c,7]<->尾
h[c] = [7, '指向LL中c节点的新指针'], h[b] = [3, '指向LL中b节点的指针'], h[a] = [5, '指向a节点的指针在 LL'],
最小窗口 => 尾部和头部的区别 => (7-3)+1 => 长度:5

等等..

请注意，上面的链表更新和哈希表更新都是 O(1)。
如果我错了请纠正我..

---

总结:

时间复杂度:O(n) 一次通过
空间复杂度:O(k) 其中 k 是字符串 Y 的长度