Grokking Newsletter 241

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) {
            return new ArrayList<>();
        }

        final Map<Character, Integer> mask = new HashMap<>();
        mask.put('A', 0);
        mask.put('C', 1);
        mask.put('G', 2);
        mask.put('T', 3);

        int hash = 0;
        int windowLen = 10;
        int base = 4;
        int basePow = (int) Math.pow(base, windowLen - 1);
        Set<String> result = new HashSet<>();
        Set<Integer> seen = new HashSet<>();

        for (int i = 0; i < windowLen; i++) {
            hash = hash * base + mask.get(s.charAt(i));
        }
        seen.add(hash);

        for (int i = 1; i <= s.length() - windowLen; i++) {
            hash -= basePow * mask.get(s.charAt(i - 1));
            hash = hash * base + mask.get(s.charAt(i + windowLen - 1));

            if (!seen.add(hash)) {
                result.add(s.substring(i, i + windowLen));
            }
        }

        return new ArrayList<>(result);
    }
}