hihoCoder 1485-hiho字符串

---

如果字符串中包含2个h，1个i和1个o，则称该子串为hiho字符串。给定一个字符串s，问s中最短的hiho子串长度是多少。如果不存在hiho子串，则输出-1。 首先，肯定不能用两层循环暴力解法，这样的话需要$$O(n^3)$$，因为判断子串是否是hiho串还需要O(n)，所以乘起来就是$$O(n^3)$$。 我当时的解法是，首先扫一遍字符串，记录下每个位置及其前面出现的h,i,o字符总数。然后我使用两层循环，把对应位置的h,i,o数目作差，如果等于2,1,1，则更新结果。但是$$O(n^2)$$的复杂度还是TLE了。 看了下第一名的解法，虽然复杂度也是$$O(n^2)$$，但是高明许多。设置两个指针i,j，区间[i,j]相当于一个滑动窗口，对于每个i，j往后走，直到h,i,o次数不低于2,1,1，如果正好是2,1,1，则把当前长度j-i和结果比较。i往后走时，对应的s[i]频率要减1。 代码如下，注意第23行，必须是大于号，不能是大于等于，因为如果只是hash[‘o’]==1就跳出的话，假设输入字符串是”oihateher”，则第0位时hash[‘o’]==1，此时跳出，导致起点i变成了1而找不到正确结果。具体用这个样例测试一下就知道。 [cpp] #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; const int MAXN = 100005; int main() { string s; cin >> s; //s = "oihateher"; int n = s.size(); if (n < 4) { cout << -1; return 0; } vector<int> hash(256, 0); int ans = MAXN; for (int i = 0, j = 0; i < n; ++i) { while (j < n && (hash[‘h’] < 2 || hash[‘i’] < 1 || hash[‘o’] < 1)) { ++hash[s[j++]]; if (hash[‘h’] > 2 || hash[‘i’] > 1 || hash[‘o’] > 1)break; } if (hash[‘h’] == 2 && hash[‘i’] == 1 && hash[‘o’] == 1) ans = min(ans, j – i); –hash[s[i]]; } if (ans == MAXN)cout << -1; else cout << ans; return 0; } [/cpp] 本代码提交AC，用时13MS。]]>