class Solution:
    s = ""; k = 0; p = 0; found = []
    def init(self, s: str, k: int, m: int, u: int):
        self.s = s; self.k = k; self.p = 1 << m; self.found = [False]*u
    def suffix(self, s: str, n: int, m: int) -> int:
        x = 0; p = 1; i = n-1
        while m > 0:
            if self.s[i] == '1':
                x += p
            m -= 1; p = p << 1
        return x 
    def has_all_codes(self, i: int, u: int, x: int) -> bool:    
        if u == 0:
            return True
        if i < 0:
            return False
        if self.s[i] == '1':
            x += self.p
        if not self.found[x]:
            u -= 1; self.found[x] = True
        return self.has_all_codes(i-1,u,x>>1)
    def hasAllCodes(self, s: str, k: int) -> bool:
        m = k-1; n = len(s); q = n-k+1; u = 1 << k 
        if q < u:
            return False
        self.init(s,k,m,u)
        return self.has_all_codes(q-1,u,self.suffix(s,n,m))

Y2xhc3MgU29sdXRpb246CiAgICBzID0gIiI7IGsgPSAwOyBwID0gMDsgZm91bmQgPSBbXQogICAgZGVmIGluaXQoc2VsZiwgczogc3RyLCBrOiBpbnQsIG06IGludCwgdTogaW50KToKICAgICAgICBzZWxmLnMgPSBzOyBzZWxmLmsgPSBrOyBzZWxmLnAgPSAxIDw8IG07IHNlbGYuZm91bmQgPSBbRmFsc2VdKnUKICAgIGRlZiBzdWZmaXgoc2VsZiwgczogc3RyLCBuOiBpbnQsIG06IGludCkgLT4gaW50OgogICAgICAgIHggPSAwOyBwID0gMTsgaSA9IG4tMQogICAgICAgIHdoaWxlIG0gPiAwOgogICAgICAgICAgICBpZiBzZWxmLnNbaV0gPT0gJzEnOgogICAgICAgICAgICAgICAgeCArPSBwCiAgICAgICAgICAgIG0gLT0gMTsgcCA9IHAgPDwgMQogICAgICAgIHJldHVybiB4IAogICAgZGVmIGhhc19hbGxfY29kZXMoc2VsZiwgaTogaW50LCB1OiBpbnQsIHg6IGludCkgLT4gYm9vbDogICAgCiAgICAgICAgaWYgdSA9PSAwOgogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGlmIGkgPCAwOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICBpZiBzZWxmLnNbaV0gPT0gJzEnOgogICAgICAgICAgICB4ICs9IHNlbGYucAogICAgICAgIGlmIG5vdCBzZWxmLmZvdW5kW3hdOgogICAgICAgICAgICB1IC09IDE7IHNlbGYuZm91bmRbeF0gPSBUcnVlCiAgICAgICAgcmV0dXJuIHNlbGYuaGFzX2FsbF9jb2RlcyhpLTEsdSx4Pj4xKQogICAgZGVmIGhhc0FsbENvZGVzKHNlbGYsIHM6IHN0ciwgazogaW50KSAtPiBib29sOgogICAgICAgIG0gPSBrLTE7IG4gPSBsZW4ocyk7IHEgPSBuLWsrMTsgdSA9IDEgPDwgayAKICAgICAgICBpZiBxIDwgdToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICAgICAgc2VsZi5pbml0KHMsayxtLHUpCiAgICAgICAgcmV0dXJuIHNlbGYuaGFzX2FsbF9jb2RlcyhxLTEsdSxzZWxmLnN1ZmZpeChzLG4sbSkp