aboutsummaryrefslogtreecommitdiff
path: root/check_string_cont_k.cpp
blob: e041052fb03e9df22cc4eedf8494adaaff9d157d (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
#include "leetcode.h"

class Solution {
public:
  bool hasAllCodes(string s, int k) {
    int bitLimit = 1 << k, n = 0;
    bool combos[bitLimit];
    for (int i = 0; i < bitLimit; i++)
      combos[i] = true;
    for (int i = 0, limit = k - 1; i < limit; i++)
      n = (n << 1) + (s[i] == '1');
    for (int i = k - 1, limit = s.size(), total = bitLimit; i < limit; i++) {
      n = (n << 1) + (s[i] == '1');
      if (n >= bitLimit)
        n -= bitLimit;
      if (combos[n])
        combos[n] = false, total--;
      if (!total)
        return true;
    }
    return false;
  }
};

int main() {
  Solution obj;
  string s = "00110110";
  int k = 2;
  cout << obj.hasAllCodes(s, k);
}