hiho #1485 : hiho字符串(滑动窗口)

#1485 : hiho字符串

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

如果一个字符串恰好包含2个'h'、1个'i'和1个'o'，我们就称这个字符串是hiho字符串。

例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。

现在给定一个只包含小写字母的字符串S，小Hi想知道S的所有子串中，最短的hiho字符串是哪个。

输入

字符串S

对于80%的数据，S的长度不超过1000

对于100%的数据，S的长度不超过100000

输出

找到S的所有子串中，最短的hiho字符串是哪个，输出该子串的长度。如果S的子串中没有hiho字符串，输出-1。

样例输入

happyhahaiohell

样例输出

思路：

在给定的字符串S中找到最小的窗口使其完全包含hiho。不能多也不能少，

时间复杂度：O(l1+4)（l1为字符串S的长度）

空间复杂度：O(4)

AC代码：

#include "iostream"
#include "string"
#include "string.h"
#include "vector"
#include "map"
#include "algorithm"

using namespace std;

char c[256];
int ans = 100005;

int main()
{
    string s;
    while (cin >> s)
    {
        memset(c, 0, sizeof(c));
        int l = s.length();
        for (int i = 0,j=0; i < l; i++)
        {
            while (j < l && (c['h'] < 2 || c['i'] < 1 || c['o'] < 1))
            {
                c[s[j]]++;
                j++;
                if (c['h'] > 2 || c['i'] > 1 || c['o'] > 1)
                    break;
            }
            
            if (c['h'] == 2 && c['i'] == 1 && c['o'] == 1)
            {
                ans = min(ans, j - i);
            }
            c[s[i]]--;
        }
        if (ans == 100005)
            ans = -1;
        cout << ans << endl;
    }
}

附上LeetCode上一题类似的滑动窗口问题

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

代码：

 1 #include "iostream"
 2 #include "string"
 3 #include "string.h"
 4 using namespace std;
 5 
 6 string str;
 7 int ans = 100005;
 8 
 9 int count1[256];
10 int count2[256];
11 
12 string minWindow(string S, string T) {
13     if (T.size() == 0 || S.size() == 0)
14         return "";
15 
16     memset(count1, 0, sizeof(count1));
17     memset(count2, 0, sizeof(count2));
18 
19     for (int i = 0; i < T.size(); i++)
20     {
21         count1[T[i]]++;
22         count2[T[i]]++;
23     }
24 
25     int count = T.size();
26 
27     int start = 0;
28     int minSize = 100005;
29     int minStart;
30     for (int end = 0; end < S.size(); end++)
31     {
32         if (count2[S[end]] > 0)
33         {
34             count1[S[end]]--;
35             if (count1[S[end]] >= 0)
36                 count--;
37         }
38         if (count == 0)
39         {
40             while (true)
41             {
42                 if (count2[S[start]] > 0)
43                 {
44                     if (count1[S[start]] < 0)
45                         count1[S[start]]++;
46                     else
47                         break;
48                 }
49                 start++;
50             }
51 
52             if (minSize > end - start + 1)
53             {
54                 minSize = end - start + 1;
55                 minStart = start;
56             }
57         }
58     }
59 
60     if (minSize == ans)
61         return "";
62 
63     string ret(S, minStart, minSize);//string 构造函数
64     return ret;
65 }
66 
67 int main()
68 {
69     while (cin >> str)
70     {
71         int l = minWindow(str, "hiho").length();
72         if (l<4)
73             cout << -1 << endl;
74         else
75             cout << l << endl;
76     }
77 }

View Code