Repeated DNA Sequences (Fixed Window Hashing)

Problem

Given a DNA sequence string, return all 10-letter-long substrings that occur more than once.

Input:  s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]

Python Solution

def find_repeated_dna_sequences(s):
    seen = set()
    repeated = set()
    for i in range(len(s) - 9):
        window = s[i:i + 10]
        if window in seen:
            repeated.add(window)
        else:
            seen.add(window)
    return list(repeated)

C++ Solution

vector<string> findRepeatedDnaSequences(string s) {
    unordered_set<string> seen, repeated;
    for (int i = 0; i + 10 <= s.size(); i++) {
        string window = s.substr(i, 10);
        if (seen.count(window)) repeated.insert(window);
        else seen.insert(window);
    }
    return vector<string>(repeated.begin(), repeated.end());
}

Java Solution

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> seen = new HashSet<>();
        Set<String> repeated = new HashSet<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String window = s.substring(i, i + 10);
            if (!seen.add(window)) repeated.add(window);
        }
        return new ArrayList<>(repeated);
    }
}

Complexity

Time: O(n · 10) — effectively O(n), since each of the n-9 fixed-size windows costs O(10) to extract and hash. Space: O(n) for the sets, which can hold up to n distinct 10-letter windows.