HelloWorld.java

// https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=506633

import java.util.*;
public class HelloWorld{

     public static void main(String []args){
         
         // k = 1
         System.out.println(HelloWorld.solve("10", 1)); // true
         System.out.println(HelloWorld.solve("0", 1)); // false
         System.out.println(HelloWorld.solve("1", 1)); // false
         
         // k = 2
         System.out.println(HelloWorld.solve("00101101", 2)); // true
         System.out.println(HelloWorld.solve("0010110001", 2)); // true
         System.out.println(HelloWorld.solve("00101100", 2)); // false
         
         // k = 3
         System.out.println(HelloWorld.solve("001010011100101110111000", 3)); // true
         System.out.println(HelloWorld.solve("001010011100000101110111111000", 3)); // true
         System.out.println(HelloWorld.solve("00101001110010111011000", 3)); // false
         
     }
     
     // overall time complexity: best => O(n * k), worst => O(n * k * 2 ^ k)
     // 换用red black tree: guarantee O(n * k * k)
     public static boolean solve(String s, int k) {
         int setSize = 1 << k;
         ArrayList<Set<Set<String>>> buffer = new ArrayList<>();
         for(int i = 0; i < k; i++) {
             Set<Set<String>> ss = new HashSet<>();
             ss.add(new HashSet<>());
             buffer.add(ss);
         }
         
         for(int i = 0; i < s.length() - k + 1; i++) { // O(n), n = s.length()
             Set<Set<String>> prev = buffer.get(i % k);
             Set<Set<String>> cur = new HashSet<>();
             cur.add(new HashSet<>());
             for(Set<String> dependee: prev) { // worst case O(k)
                 dependee.add(s.substring(i, i + k));
                 if(dependee.size() == setSize) return true;
                 cur.add(dependee); // 重复检测, 用hash set, best case O(1), worst case O(2 ^ k), 如果用red black tree可以guarantee O(log(2 ^ k)) = O(k)
             }
             buffer.set(i % k, cur);
         }
         return false;
     }
}