Description

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"].

Solution

Bit-manipulation & HashMap, time O(n), space O(n)

为了判断sequence的重复性，可以对String做hash。由于DNA str的长度为10，且只由四个字符组成，很自然可以想到将DNA转换成二进制表达，每个字符由2 bits表示，那么只需要20 bits即可表达一条DNA。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> dup = new ArrayList<>();
        if (s == null || s.length() < 11) {
            return dup;
        }
        
        Map<Integer, Integer> dnaFreq = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();
        String t = "ACGT";
        for (int i = 0; i < t.length(); ++i) {
            map.put(t.charAt(i), i);
        }
        
        int val = 0;
        for (int i = 0; i < 10; ++i) {
            val = (val << 2) | map.get(s.charAt(i));
        }
        dnaFreq.put(val, 1);
        
        final int MASK = ~(3 << 18);
        for (int i = 10; i < s.length(); ++i) {
            val &= MASK;    // remove the val of s.charAt(i - 10)
            val = (val << 2) | map.get(s.charAt(i));
            dnaFreq.put(val, dnaFreq.getOrDefault(val, 0) + 1);
            
            if (dnaFreq.get(val) == 2) {    // duplicate
                dup.add(s.substring(i - 9, i + 1));
            }
        }
        
        return dup;
    }
}