1461. Check If a String Contains All Binary Codes of Size K

MediumView on LeetCode

Hash Table String Bit Manipulation Rolling Hash Hash Function

Time: O(n)

Space: O(2^k)

Intuition

Check if all binary strings of length k appear as substrings. Use a sliding window of size k and a HashSet.

Algorithm

1Slide window of size k over s. Add each window to a set.
2Return set.size() == 2^k.

Common Pitfalls

•Need exactly 2^k distinct substrings. For large k this is just checking if s is long enough.

1461.cs

// Approach: Sliding window of length k with rolling bitwise update; mark each window value in a boolean array; check all 2^k are seen.
// Time: O(n) Space: O(2^k)

public class Solution
{
    public bool HasAllCodes(string s, int k)
    {
        int n = 1 << k;
        if (s.Length < n)
            return false;

        bool[] used = new bool[n];

        int window = k == 1 ? 0 : Convert.ToInt32(s.Substring(0, k - 1), 2);
        for (int i = k - 1; i < s.Length; ++i)
        {
            window = (window << 1) + (s[i] - '0');
            window &= n - 1;
            used[window] = true;
        }

        return used.All(u => u);
    }
}

Was this solution helpful?