在 O(n) 中使用 Hash Table 在字符串 S 中查找包含字符串 T 中所有字符的最小长度子字符串

Question

我知道这个问题已经被问了不止once.My 疑惑不是找到这个问题的解法，而是正确的复杂度。我在这里阅读了一个答案：

Minimum window width in string x that contains all characters in string y
在这个解决方案中，提出的复杂度是 O(n) 使用 hash table.Now 直到将字符串 T 的字符映射到 hash table 中是可以的，但是当涉及到从 hash 中找到最小和最大元素时table，几乎每一个回答，我都看到使用了链表，他们写道，更新链表的复杂度是O(1)。这就是疑问所在。

请考虑以下示例：

S:abcbae

T:abc

初始t["a"],t["b"]和t["c"]为-1，经过3次后分别为0,1,2 （在散列 table 中）并且双链表将包含元素 [(a,0)-(b,1)-(c,2)].

现在字符串 S 中的第四个字符是 b，所以在 DLL 中为 b 添加新的索引值之前，我需要删除它之前的实例，我必须为此遍历 DLL。

我的问题是更新DLL的解决方案是O(1)，不是O(n)，这会导致总复杂度O(n^2)吗？

[O(n)遍历字符串S，然后O(n)更新DLL]

如有错误请指正。

Answer 1

描述的数据结构是一个双向链表，可视化如下，使用answer中的例子：

HEAD <=> ('c', 0) <=> ('b', 3) <=> ('a', 5) <=> TAIL

加上数组，可视化如下：

      'a'      |      'b'      |      'c'
 {5, &list[2]} | {3, &list[1]} | {0, &list[0]}

（注意信息重复）

在所描述算法的任何时候，都需要进行以下操作：

在数组中插入一个元素
在列表中插入一个元素
查找给定字符的索引值
从列表中删除一个节点

#1 的时间复杂度为 O(1)（平凡），#2 的时间复杂度也为 O(1)，因为我们选择了双向链表。

#3 的时间复杂度也是 O(1)，因为我们选择了数组。对于哈希 table 支持的映射，它仍然是 O(1)。

#4 的时间复杂度为 O(1)，因为我们的数组包含指向列表中每个节点的指针，并且每个字符在列表中只有一个节点，因此删除也是微不足道的。

重要的是要注意（并理解）这里在所提出算法的任何迭代中，最小值 window 不能大于上一步中已经存在的值（为什么？证明它），因此我们只需要每个字符最多个节点在字符串Y（或你的问题中的T）中。

希望对您有所帮助。

在 O(n) 中使用 Hash Table 在字符串 S 中查找包含字符串 T 中所有字符的最小长度子字符串

Finding a minimum length substring in string S which contains all characters from string T using Hash Table in O(n)

string

algorithm

hash

hashtable