1205 - 最短包含字符串


利用尺取法,逐个遍历输入字符 s ,同时对每种字符的数量做计数,令当前字符的计数 +1,直到所有字符的计数都大于 1 为止。

此时从起始位置 start 到当前位置 i 的字符,就是一个包含了 26 个字符的合法字符串。但并不是以 i 为结尾最短的合法字符串,此时我们让 start 向后走,同时维护字符的计数,每走一步, start 对应位置的字符记数 −1 。直到 start字符计数恰好为 1 ,如果继续向后走,则不满足包含 26个字符的条件。此时得到的,才是以 i 为结尾最短的合法字符串。

让 i 继续向后,重复上面的过程,途中记录所有合法字符长度的最小值即可。复杂度 O(n)