# Repeated DNA Sequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/repeated-dna-sequences)
Canonical: https://scaleengineer.com/dsa/problems/repeated-dna-sequences
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** Hash Table, String
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Tesla](https://scaleengineer.com/companies/tesla), [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
The **DNA sequence** is composed of a series of nucleotides abbreviated as `'A'`, `'C'`, `'G'`, and `'T'`.

* For example, `"ACGAATTCCG"` is a **DNA sequence**.

When studying **DNA**, it is useful to identify repeated sequences within the DNA.

Given a string `s` that represents a **DNA sequence**, return all the **`10`\-letter-long** sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in **any order**.

**Example 1:**

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

**Example 2:**

**Input:** s = "AAAAAAAAAAAAA"
**Output:** ["AAAAAAAAAA"]

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is either `'A'`, `'C'`, `'G'`, or `'T'`.

# Approaches
## Brute Force
This approach involves a straightforward, nested-loop comparison. We take every possible 10-letter substring and compare it with every subsequent 10-letter substring in the sequence. A `HashSet` is used to store the found repeated sequences to ensure the final output contains only unique entries.
**Time:** O(N^2 * L) · **Space:** O(K * L)
**Pros:** Simple to conceptualize and implement.; Does not require complex data structures.
**Cons:** Extremely inefficient with a quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error for large inputs.; Performs a large number of redundant string comparisons.
### Explanation
The brute-force method is the most intuitive way to solve the problem. We generate all possible 10-letter substrings starting from each index `i`. For each of these substrings, we then scan the rest of the string from index `i+1` onwards to see if an identical substring exists. If a match is found, we add the substring to a `HashSet` to automatically handle duplicates in the final result. While simple, this method's performance degrades rapidly as the input string size increases due to its O(N^2) nature.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        if (n <= 10) {
            return new ArrayList<>();
        }
        Set<String> result = new HashSet<>();
        // Iterate through all possible start indices of a 10-letter substring
        for (int i = 0; i <= n - 10; i++) {
            String sub1 = s.substring(i, i + 10);
            // Compare with all subsequent 10-letter substrings
            for (int j = i + 1; j <= n - 10; j++) {
                String sub2 = s.substring(j, j + 10);
                if (sub1.equals(sub2)) {
                    result.add(sub1);
                    break; // Found a repeat, no need to check further for sub1
                }
            }
        }
        return new ArrayList<>(result);
    }
}
```
### Algorithm
- Initialize an empty set `result` to store the unique repeated sequences.
- Iterate through the string `s` with an index `i` from the beginning up to the point where a 10-letter substring can be formed (`s.length() - 10`).
- For each `i`, extract the substring `sub1 = s.substring(i, i + 10)`.
- Start a nested loop with an index `j` from `i + 1` to `s.length() - 10`.
- In the inner loop, extract the substring `sub2 = s.substring(j, j + 10)`.
- If `sub1` is equal to `sub2`, it means we have found a repeated sequence. Add `sub1` to the `result` set.
- To avoid redundant checks for `sub1`, we can break the inner loop once a match is found.
- After the loops complete, convert the `result` set into a list and return it.

## Linear Scan with Hash Set
A more optimized approach uses a `HashSet` to keep track of substrings we've already seen. We iterate through the string's 10-letter substrings only once. For each substring, we check if it's already in our `seen` set. If it is, we've found a repeat and add it to a separate `repeated` set. If it's not, we add it to the `seen` set. This avoids the expensive nested loop of the brute-force method.
**Time:** O((N - L) * L) · **Space:** O((N - L) * L)
**Pros:** Much more efficient than the brute-force approach, with a linearithmic time complexity.; Easy to implement using standard library hash sets.
**Cons:** The time complexity is affected by the cost of creating and hashing substrings of length L, making it O(N*L) instead of O(N).; The space complexity can be high, as it requires storing the actual string objects in the hash set, which can consume significant memory for a large number of unique substrings.
### Explanation
This method improves upon the brute-force approach by leveraging the constant-time average complexity of hash set operations. We slide a window of length 10 over the string from left to right. For each 10-letter substring, we use two sets: `seen` and `repeated`. The `seen` set stores every unique substring we encounter. If we try to add a substring to `seen` and it's already there, we know it's a repeat. We then add this repeated substring to the `repeated` set. Using a set for the results ensures that even if a sequence is repeated multiple times (e.g., `"AAAAAAAAAAA"`), the result `"AAAAAAAAAA"` is only stored once.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

        Set<String> seen = new HashSet<>();
        Set<String> repeated = new HashSet<>();

        for (int i = 0; i <= n - 10; i++) {
            String sub = s.substring(i, i + 10);
            if (!seen.add(sub)) {
                // If add returns false, it means the substring was already in the set.
                repeated.add(sub);
            }
        }
        return new ArrayList<>(repeated);
    }
}
```
### Algorithm
- Initialize two hash sets: `seen` to store every unique 10-letter substring encountered, and `repeated` to store the substrings that appear more than once.
- Iterate through the string `s` with a single loop, from index `i = 0` to `s.length() - 10`.
- In each iteration, extract the 10-letter substring `current = s.substring(i, i + 10)`.
- Attempt to add `current` to the `seen` set. The `add` method of a `HashSet` returns `false` if the element is already present.
- If `seen.add(current)` returns `false`, it signifies that we have encountered this substring before, so it is a repeated sequence. Add `current` to the `repeated` set.
- The `repeated` set automatically handles duplicates, so a sequence repeated three or more times is only added once.
- After the loop finishes, convert the `repeated` set to a list and return it.

## Rolling Hash with Bit Manipulation
The most optimal approach uses a rolling hash technique combined with bit manipulation. Each of the 4 DNA characters can be represented by 2 bits. Therefore, any 10-letter sequence can be encoded into a unique 20-bit integer. We can slide a window across the string, and for each step, we can calculate the new sequence's integer representation from the previous one in constant O(1) time using bitwise operations. This avoids creating new substrings and performs hashing much faster, leading to a true O(N) time complexity.
**Time:** O(N - L) · **Space:** O(N - L)
**Pros:** Optimal linear time complexity O(N).; Highly space-efficient as it stores compact integers in the 'seen' set instead of larger string objects.; Guaranteed no hash collisions due to the perfect mapping of sequences to integers.
**Cons:** The implementation is more complex and less intuitive than the previous approaches.; This specific bit manipulation technique is tailored to the problem's constraints (small alphabet, fixed length) and is not a general-purpose solution.
### Explanation
This approach is a highly optimized version of the rolling hash. By mapping each DNA character to a 2-bit number, we can represent any 10-letter sequence as a single 20-bit integer, which fits comfortably within a standard 32-bit `int`. This provides a perfect, collision-free hash.

The key is the 'rolling' update. Instead of recomputing the 20-bit integer for each substring, we can derive the next integer from the previous one in O(1) time. This is done by:
1. Shifting the current integer left by 2 bits (`h << 2`), which makes space for the new character and effectively starts the process of dropping the oldest character.
2. Applying a bitmask (`& ((1 << 20) - 1)`) to ensure we only keep the 20 least significant bits, which completes the removal of the oldest character's bits.
3. Using a bitwise OR to add the 2 bits of the new character at the end of the window.

This method is significantly faster and more memory-efficient because we are manipulating and storing primitive integers instead of string objects.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

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

        Map<Character, Integer> toInt = new HashMap<>() {{
            put('A', 0); put('C', 1); put('G', 2); put('T', 3);
        }};

        Set<Integer> seen = new HashSet<>();
        Set<String> output = new HashSet<>();
        
        int bitmask = (1 << (L * 2)) - 1; // A mask for 20 bits (10 letters * 2 bits)
        int currentHash = 0;

        // Calculate hash for the first window
        for (int i = 0; i < L; i++) {
            currentHash = (currentHash << 2) | toInt.get(s.charAt(i));
        }
        seen.add(currentHash);

        // Roll the window over the rest of the string
        for (int i = 1; i <= n - L; i++) {
            // Update hash: shift left, mask to remove old bits, and add new bits
            currentHash = ((currentHash << 2) & bitmask) | toInt.get(s.charAt(i + L - 1));
            
            if (!seen.add(currentHash)) {
                // If add returns false, the hash (and thus the sequence) has been seen before
                output.add(s.substring(i, i + L));
            }
        }
        return new ArrayList<>(output);
    }
}
```
### Algorithm
- Since the alphabet is small (A, C, G, T), map each character to a 2-bit integer (e.g., A->0, C->1, G->2, T->3).
- A 10-letter sequence can be uniquely represented by a 20-bit integer (10 letters * 2 bits/letter).
- Initialize two sets: `seen` to store the integer representations of encountered sequences, and `output` to store the actual repeated string sequences.
- Calculate the integer representation for the first 10-letter window by iterating through its characters and using bitwise left-shift and OR operations.
- Add this first integer representation to the `seen` set.
- Now, iterate from the second character of the string to the end, 'rolling' the window one character at a time.
- In each step, update the integer representation in O(1) time: left-shift the current integer by 2, apply a 20-bit mask to remove the oldest character's bits, and OR with the new character's 2-bit value.
- If adding the new integer to `seen` fails (i.e., it's a duplicate), add the corresponding 10-letter substring to the `output` set.
- Finally, return the `output` set as a list.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < string > FindRepeatedDnaSequences(string s) {
        var cnt = new Dictionary < string,
            int > ();
        var ans = new List < string > ();
        for (int i = 0; i < s.Length - 10 + 1; ++i) {
            var t = s.Substring(i, 10);
            if (!cnt.ContainsKey(t)) {
                cnt[t] = 0;
            }
            if (++cnt[t] == 2) {
                ans.Add(t);
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<String> findRepeatedDnaSequences(String s) {
    Map<String, Integer> cnt = new HashMap<>();
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < s.length() - 10 + 1; ++i) {
      String t = s.substring(i, i + 10);
      if (cnt.merge(t, 1, Integer : : sum) == 2) {
        ans.add(t);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {string[]} */ var findRepeatedDnaSequences = function ( s ) { const cnt = new Map (); const ans = []; for ( let i = 0 ; i < s . length - 10 + 1 ; ++ i ) { const t = s . slice ( i , i + 10 ); cnt . set ( t , ( cnt . get ( t ) || 0 ) + 1 ); if ( cnt . get ( t ) === 2 ) { ans . push ( t ); } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<string, int> cnt;
    vector<string> ans;
    for (int i = 0, n = s.size() - 10 + 1; i < n; ++i) {
      auto t = s.substr(i, 10);
      if (++cnt[t] == 2) {
        ans.emplace_back(t);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    # for encoded words repeated = set () # for encoded words result = [] # not encoded words # A => binary: 00 # C => binary: 01 # G => binary: 10 # T => binary: 11 mapping = { 'A' : 0 , 'C' : 1 , 'G' : 2 , 'T' : 3 } for i in range ( len ( s ) - 9 ): v = 0 for j in range ( i , i + 10 ): # every time, use the new 2 bits after shifting for current char v <<= 2 v |= mapping [ s [ j ]] if v in words and v not in repeated : repeated . add ( v ) result . append ( s [ i : i + 10 ]) words . add ( v ) return result ############ class Solution : def findRepeatedDnaSequences ( self , s : str ) -> List [ str ]: n = len ( s ) - 10 cnt = Counter () ans = [] for i in range ( n + 1 ): sub = s [ i : i + 10 ] cnt [ sub ] += 1 if cnt [ sub ] == 2 : ans . append ( sub ) return ans
    def findRepeatedDnaSequences(self, s: str) -> List[str]: words = set()

```