【LeetCode 1461】Check If a String Contains All Binary Codes of Size K 解説（Java・初心者向け）

2進数コードとは？

0 と 1 のみで構成された文字列です。

例えば：

k	存在するすべての2進数コード	個数
1	0, 1	2
2	00, 01, 10, 11	4
3	000, 001, 010, 011, 100, 101, 110, 111	8

個数は常に：2^kです。

問題の意味（簡単に）

文字列 s の中に、

「長さ k のすべての2進数パターン（合計 2^k 個）」が

部分文字列としてすべて存在するか確認する問題です。

なぜこれで解けるか？

長さ k のすべての2進数コードの個数は必ず：

2^k

HashSet は重複を除去するため、

HashSet のサイズ == 2^k

なら、すべてのコードが存在することになります。

---

Java実装

import java.util.HashSet;
import java.util.Set;

class Solution {

    public boolean hasAllCodes(String s, int k) {

        Set<String> set = new HashSet<>();

        // 長さ k の substring をすべて取得
        for (int i = 0; i <= s.length() - k; i++) {
            String sub = s.substring(i, i + k);
            set.add(sub);
        }

        // 必要なコード数 = 2^k
        int need = 1 << k;

        return set.size() == need;
    }
}