# 强迫症的真真## 题目背景真真患上了强迫症比如每天早上都要吃两个包子## 题目描述真真发现他对字符串也有强迫症他喜欢的字符串必须恰好包含3个z。例如poazdxzz、oixzzz都是真真喜欢的字符串我们称为真真串。但是像yuzz、deoa这样的字符串真真是非常讨厌的。现在给定一个只包含小写字母的字符串ch请你帮助真真计算ch的所有子串中最短的真真串是哪一个。对于子串我们规定：xoi、itydr

算法1

(暴力枚举) $O(n^2)$

枚举所有长度大于等于3的子串，计算其中是否存在3个z，若存在，更新答案。

时间复杂度

枚举子串的复杂度为$O(n^2)$，计算子串中有几个z的时间复杂度为$O(n)$，所以总的时间复杂度为$O(n^3)$。

算法2

(滑动窗口) $O(n)$

我们可以用两个指针l和r表示一个子串。初始时，l和r都指向字符串的开头。之后每次将r右移一位，判断l到r这个子串中是否恰好包含3个z。如果包含3个z，更新答案；如果不包含，将左指针l右移一位。这样，最终答案就是最短的包含3个z的子串。

时间复杂度

由于左指针和右指针最多各移动n次，所以总的时间复杂度为$O(n)$。

参考文献

王道考研机试指南

C++ 代码

算法1