强迫症的真真串：寻找最短的包含三个'z'的子串

强迫症的真真串：寻找最短的包含三个'z'的子串/n/n### 题目背景/n/n真真患上了强迫症，比如每天早上都要吃两个包子。/n/n### 题目描述/n/n真真发现他对字符串也有强迫症，他喜欢的字符串必须恰好包含3个'z'。/n例如'poazdxzz'、'oixzzz'都是真真喜欢的字符串，我们称为真真串。但是像'yuzz'、'deoa'这样的字符串，真真是非常讨厌的。/n现在给定一个只包含小写字母的字符串ch，请你帮助真真计算ch的所有子串中，最短的真真串是哪一个。/n对于子串，我们规定：'xoi'、'itydre'都是'xoitydre'的子串，但是'xit'不是'xoitydre'的子串。/n/n### 输入格式/n/n输入一个只包含小写字母的字符串，字符串的长度不超过100000/n/n### 输出格式/n/n若输入的字符串的所有子串中有真真串，找到最短的真真串，输出其长度。若没有真真串，则输出'zzz'（不包含引号）。/n/n### 样例 #1/n/n#### 样例输入 #1/n/n/nhappyzazziohell/n/n/n#### 样例输出 #1/n/n/n4/n/n/n### 样例 #2/n/n#### 样例输入 #2/n/n/nxoizz/n/n/n#### 样例输出 #2/n/n/nzzz/n/n/n### 思路/n/n一个 $n$ 个元素的字符串，有 $/frac {n/times(n+1)} 2$ 个子串，$n/leq 10^5$，暴力枚举不可取。/n/n考虑每次从左往右扫描字符串，维护一个区间 $[l,r]$，满足区间中包含恰好 $3$ 个 'z'，接下来我们分情况讨论：/n/n- 如果当前位置字符不是 'z'，那么区间 $[l,r]$ 就可以向右扩张，$r/gets r+1$。/n- 如果当前位置字符是 'z'，那么就算出 $[l,r]$ 中 'z' 的个数，如果大于等于 $3$，那么区间 $[l,r]$ 就可以向右扩张，$r/gets r+1$；否则，区间 $[l,r]$ 就可以向右扩张，$r/gets r+1$，直到 $[l,r]$ 中 'z' 的个数恰好为 $3$。判断当前区间是否是最短的真真串，如果是，记下答案。/n- 如果最后扫描完字符串，都没有找到真真串，那么输出 zzz。/n/n### 算法/n/n字符串模拟。/n/n时间复杂度 $O(n)$。/n/n### 代码/n/npython/ns = input().strip()/n/nbegin, end, cnt, ans = -1, -1, 0, float('inf')/nfor i in range(len(s)):/n if s[i] == 'z':/n cnt += 1/n/n while cnt > 3:/n if s[i - cnt + 3] == 'z':/n cnt -= 1/n begin += 1/n/n end += 1/n if cnt == 3 and ans > end - begin:/n ans = end - begin/n/nif ans == float('inf'):/n print('zzz')/nelse:/n print(ans)/n/n