查找具有其他字符串的所有字符的子字符串的最小长度的算法

我有两个字符串：
字符串1 -hello how are you,
字符串2 -olo（包括空格字符）

Output: lo ho ( hello ho你是谁）

lo ho是唯一包含 string2 的所有字符的子字符串。 任何人都可以为此提出一个好的算法（我只能想到暴力算法 - O(n^2)。

输出还应该是最小长度字符串（如果有多个选项）。

保留两个指针l and r，和一个哈希表M = character -> count对于 string2 中未出现的字符s[l..r].

初始设置l = 0 and r以便string1[l..r]包含所有字符string2（如果可能的话）。您可以通过从 M 中删除字符直到它为空来实现这一点。

然后继续递增r每一步加一，然后递增l尽可能多，同时仍保持 M 为空。总体上最小的r - l + 1（子串的长度s[l..r]) 就是解。

Python 伪代码：

n = len(string1)
M = {}   # let's say M is empty if it contains no positive values
for c in string2:
    M[c]++
l = 0
r = -1
while r + 1 < n and M not empty:
    r++
    M[string1[r]]--
if M not empty: 
    return "no solution"
answer_l, answer_r = l, r
while True:
    while M[string1[l]] < 0:
        M[string1[l]]++
        l++
    if r - l + 1 < answer_r - anwer_l + 1:
        answer_l, answer_r = l, r
    r++
    if r == n:
        break
    M[string1[r]]--
return s[answer_l..answer_r]

如果在执行递增和递减操作时保持正条目的数量，则可以在 O(1) 中实现“是否为空”检查。

Let n的长度是string1 and m的长度是string2.

注意l and r只会递增，因此最多有 O(n) 次递增，因此在最后一个外循环中最多执行 O(n) 条指令。

If M被实现为一个数组（我假设字母表的大小是恒定的），你得到运行时 O(n + m)，这是最优的。如果字母表太大，可以使用哈希表来获得预期的 O(n + m)。

执行示例：

string1 = "abbabcdbcb"
string2 = "cbb"

# after first loop
M = { 'a': 0, 'b': 2, 'c': 1, 'd': 0 }

# after second loop
l = 0
r = 5
M = { 'a': -2, 'b': -1, 'c': 0, 'd': 0 }

# increment l as much as possible:
l = 2
r = 5
M = { 'a': -1, 'b': 0, 'c': 0, 'd': 0 }

# increment r by one and then l as much as possible
l = 2
r = 6
M = { 'a': -1, 'b': 0, 'c': 0, 'd': -1 }

# increment r by one and then l as much as possible
l = 4
r = 7
M = { 'a': 0, 'b': 0, 'c': 0, 'd': -1 }

# increment r by one and then l as much as possible
l = 4
r = 8
M = { 'a': 0, 'b': 0, 'c': -1, 'd': -1 }

# increment r by one and then l as much as possible
l = 7
r = 9
M = { 'a': 0, 'b': 0, 'c': 0, 'd': 0 }

最好的解决方案是 s[7..9]。