1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public: bool checkInclusion(string s1, string s2) { const int n1 = s1.size(), n2 = s2.size(); if (n1 > n2) return false; vector<int> freq(26), winFreq(26); int cnt = 0, winCnt = 0; for (char c : s1) if (freq[c - 'a']++ == 0) ++cnt; int left = 0, right = 0; while (right < n2) { int idx = s2[right++] - 'a'; if (freq[idx] > 0) if (++winFreq[idx] == freq[idx]) ++winCnt; while (winCnt == cnt) { if (right - left == n1) return true; idx = s2[left++] - 'a'; if (freq[idx] > 0) if (--winFreq[idx] < freq[idx]) --winCnt; } } return false; } };
|