您可以在O(N+M)时间和O(1)空间上进行直方图扫描，其中N是第一个字符串中M的字符数，而第二个字符串中的字符数。

它是这样的：

• 制作第二个字符串的字符的直方图（键操作为hist2[ s2[i] ]++）。
• 制作第一个字符串的字符的累积直方图，直到该直方图包含第二个字符串的直方图包含的每个字符（我将其称为“直方图条件”）。
• 然后向前移动第一个字符串，从直方图中减去，直到它不满足直方图的条件。将第一个字符串的那一部分（最后一步之前）标记为您的暂定子字符串。
• 再次向前移动子字符串的前端，直到再次满足直方图条件为止。将末端向前移动，直到再次失败。如果这是比第一个短的子字符串，请将其标记为您的暂定子字符串。
• 重复直到您遍历了整个第一个字符串。
• 标记的子字符串是您的答案。

请注意，通过改变您在直方图条件上使用的检查，您可以选择具有 与 第二个字符串 相同的字符集 ，或者 每种类型的字符数最少
。（它只是之间的差异a[i]>0 && b[i]>0和a[i]>=b[i]。）

如果您跟踪想要满足的条件不满足的条件，则可以加快直方图的检查速度，并在尝试破坏条件时仅检查您递减的值。（在初始构建时，您要计算满足的项目数，并在每次添加将条件从false变为true的新字符时递增该计数。）