aboutsummaryrefslogtreecommitdiff
path: root/permutation_in_string.cpp
blob: f4e09f35dae7c199c8751cb71efc9d4e39dabd57 (plain)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 567. Permutation in String
#include "leetcode.h"

/*
 * given two strings 's1 s2' return true if 's2' contains a permutation of 's1'
 * or false otherwise. in other words, return true if one of 's1's permutations
 * is in the substring of 's2'
 */

class Solution {
public:
  bool checkInclusion(string s1, string s2) {
    if (s2.size() < s1.size())
      return false;
    vector<int> freq1(26, 0), freq2(26, 0);
    for (char c : s1)
      freq1[c - 'a']++;
    int i = 0, j = 0;
    while (j < s2.size()) {
      freq2[s2[j] - 'a']++;
      if (j - i + 1 == s1.size())
        if (cmp(freq1, freq2))
          return true;
      if (j - i + 1 < s1.size())
        j++;
      else {
        freq2[s2[i] - 'a']--;
        i++, j++;
      }
    }
    return false;
  }

private:
  bool cmp(vector<int> a, vector<int> b) {
    for (int i = 0; i < 26; i++)
      if (a[i] != b[i])
        return false;
    return true;
  }
};

int main() {
  Solution obj;
  cout << obj.checkInclusion("ab", "eidbaooo") << endl; // expect: 1
  cout << obj.checkInclusion("ab", "eidboaoo") << endl; // expect: 0
}