## Amazon Interview Question

SDE1s**Country:**United States

```
static bool ContainAllPermutations(string str,int k)
{
if (str.Count() < k * 2)
return false;
Dictionary<string, int> Permutation = new Dictionary<string, int>();
for(int i=0;i<=str.Count()-k;i++)
{
if(!Permutation.ContainsKey(str.Substring(i,k)))
{
Permutation.Add(str.Substring(i, k), 1);
}
}
if(Permutation.Count== Math.Pow(2, k))
{
return true;
}
return false;
}
```

O(n) solution, uses O(2**k) memory.

```
def foo(s, k):
if len(s) < k + 2**k - 1:
return False
(count, v) = (2**k-1, [0]*2**k)
q = reduce(lambda a,b:2*a+b, s[:k], 0)
v[q] = 1
z = 2**(k-1)
for si in xrange(len(s)-k):
q = (q-s[si]*z)*2+s[si+k]
if v[q] == 0:
v[q] = 1
count -= 1
if count == 0:
return True
return False
print foo([1, 0, 0, 1, 1], 2)
```

- guilhebl May 24, 2018