import java.util.*;

/**
 * All DNA is composed of a series of nucleotides abbreviated as A, C, G, and 
 * T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to 
 * identify repeated sequences within the DNA.
 * 
 * Write a function to find all the 10-letter-long sequences (substrings) that
 * occur more than once in a DNA molecule.
 * 
 * For example,
 * 
 * Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
 * 
 * Return:
 * ["AAAAACCCCC", "CCCCCAAAAA"].
 * 
 * Tags: Bit Manipulation
 */
class RepeatedDNASeq {
    public static void main(String[] args) {
        
    }
    
    /**
     * To optimize space usage, map string to other key that won't collide
     * Design a hash function according to observation
     * A: 0x41, C: 0x43, G: 0x47, T: 0x54, last 3 bits are different
     * 10 chars, each 3 bits, 10 x 3 = 30 bits < 32
     * 
     * Key: an int to record the bit mask of current substring, 
     * Value: a boolean, true means showed up before, false means already added
     * Update the map
     */
    public List<String> findRepeatedDnaSequences(String s) {
        if (s == null || s.length() < 10) return Collections.EMPTY_LIST;
        List<String> res = new ArrayList<>();
        Map<Integer, Boolean> map = new HashMap<>();
        for (int t = 0, i = 0; i < s.length(); i++) {
            t = (t << 3 & 0x3FFFFFFF) | (s.charAt(i) & 7);
            if (map.containsKey(t)) {
                if (map.get(t)) {
                    res.add(s.substring(i - 9, i + 1));
                    map.put(t, false);
                }
            } else {
                map.put(t, true);
            }
        }
        return res;
    }
    
    /**
     * HashSet with previous appeared results
     * O(n) Space
     */
    public List<String> findRepeatedDnaSequencesB(String s) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() < 10) return res;
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < s.length() - 10; i++) {
            String sub = s.substring(i, i + 10);
            if (set.contains(sub)) {
                res.add(s);
            }
            set.add(s);
        }
        return res;
    }
}

@@ -1,22 +1,231 @@
-import java.util.*
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Collections;%0Aimport java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.Set
 ;%0A%0A/
@@ -305,20 +305,16 @@
  G, and 
-%0A * 
 T, for e
@@ -339,16 +339,19 @@
 G%22. When
+%0A *
  studyin
@@ -383,20 +383,16 @@
 eful to 
-%0A * 
 identify
@@ -426,24 +426,27 @@
 the DNA.%0A * 
+%3Cp%3E
 %0A * Write a 
@@ -512,19 +512,16 @@
 gs) that
-%0A *
  occur m
@@ -552,24 +552,27 @@
 olecule.%0A * 
+%3Cp%3E
 %0A * For exam
@@ -575,24 +575,27 @@
 example,%0A * 
+%3Cp%3E
 %0A * Given s 
@@ -631,24 +631,27 @@
 GGGTTT%22,%0A * 
+%3Cp%3E
 %0A * Return:%0A
@@ -690,17 +690,51 @@
 %0A * 
-%0A * Tags:
+Company Tags: LinkedIn%0A * Tags: Hash Table,
  Bit
@@ -751,16 +751,23 @@
 ion%0A */%0A
+public 
 class Re
@@ -782,83 +782,61 @@
 ASeq
- %7B%0A    public static void main(String%5B%5D args)
+uence
  %7B%0A
+%0A
     
-    
+/**
 %0A    
-%7D%0A    %0A    /**
+ * Hash Table. Bit Manipulation.
 %0A   
@@ -906,16 +906,17 @@
  collide
+.
 %0A     * 
@@ -962,16 +962,17 @@
 ervation
+.
 %0A     * 
@@ -1032,16 +1032,17 @@
 ifferent
+.
 %0A     * 
@@ -1093,16 +1093,19 @@
 %0A     * 
+%3Cp%3E
 %0A     * 
@@ -1160,17 +1160,16 @@
 bstring,
- 
 %0A     * 
@@ -1365,32 +1365,46 @@
 s.length() %3C 10)
+ %7B%0A           
  return Collecti
@@ -1411,19 +1411,30 @@
 ons.
-EMPTY_LIST;
+emptyList();%0A        %7D
 %0A   
@@ -1932,20 +1932,16 @@
 ;%0A    %7D%0A
-    
 %0A    /**
@@ -1933,32 +1933,70 @@
 %0A    %7D%0A%0A    /**%0A
+     * Hash Table. O(n) Time & Space.%0A
      * HashSet w
@@ -2028,26 +2028,9 @@
 ults
-%0A     * O(n) Space
+.
 %0A   
@@ -2108,104 +2108,142 @@
     
-List%3CString%3E re
+if (
 s =
+=
  n
-ew ArrayList%3CString%3E();%0A        if (s == null %7C%7C s.length() %3C 10) return res
+ull %7C%7C s.length() %3C 10) %7B%0A            return Collections.emptyList();%0A        %7D%0A        List%3CString%3E res = new ArrayList%3C%3E()
 ;%0A  
@@ -2278,22 +2278,16 @@
 HashSet%3C
-String
 %3E();%0A   

update repeated dna sequence