Repeated DNS Sequence

Given a string, s, that represents a DNA subsequence, and a number k, return all the contiguous subsequences (substrings) of length k that occur more than once in the string. The order of the returned subsequences does not matter. If no repeated substring is found, the function should return an empty set.

Note

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 in it.

Constraints

• 1 ≤ s.length ≤ 10⁴
• s[i] is either A, C, G, or T.
• 1 ≤ k ≤ 10

Examples

Sample Example 1

Input:

• s = "GAGTCACAGTAGTTTCA"
• k = 3

Output:

• Sequence 1 = "AGT"
• Sequence 2 = "TCA"

Explanation: "AGT" appears twice in s (as a repeated sequence of length k = 3), and "TCA" also appears twice in s.

Sample Example 2

Input:

• s = "CAAACCCCGTAAACCCCA"
• k = 7

Output:

• Sequence 1 = "AAACCCC"

Explanation: "AAACCCC" appears twice in s (as a repeated sequence of length k = 7).

Naive Solution

The first approach I see to solve this problem is to find the list of all possible k-length substrings and keep track of whether they are not unique.

function repeatedDNS(s, k) {
    let start = 0;
    let map = new Map();
    let result = new Set();
    for (let end = k; end <= s.length; end++) {
        let curr = s.slice(start, end);
        if (map.has(curr)) {
            result.add(curr);
        }
        map.set(curr, 1);
        start++;
    }
    return result;
}
console.log(repeatedDNS('GAGTCACAGTAGTTTCA', 3));

Complexity

Time: The loop runs from k to n times, which means n - k + 1 iterations, so O(N) for the loop. Inside the loop, there is a slice statement that copies k characters, so O(K). Finding and storing a value of length k in the map would also be O(K).

Combined Time Complexity:

O(N) × ( O(K) + O(K) + O(K) )

O(NK)

Space: To find the space complexity, we focus on the data structures that grow with input.

• curr = s.slice(start, end) takes O(K) space.
• The map will store a total of n - k + 1 entries in the worst case (assuming all are unique), and each key would be of length K, giving O(NK).
• result will also store n - K + 1 of k length giving O(NK).

Overall Space Complexity: O(NK)

Optimized Solution

The naive solution was very straightforward and is perfect for Constraints I got which restrict value of K above 10 but if K value is huge The space complexity becomes a huge concerning factor let's suppose K value is 10000 our each substr would look like abcd.... now performing operation on it will cost much higher time complexity as well. To solve this problem, I will hash our substr and then store it. Also, I need to make sure generating hash of next substring should be cheap else the new solution won't make any sense.

Rolling Hash OR Rabin Karp Algorithm In Rolling Hash algo we'll generate a hash for given substring and store it, if at any point the hash gets repeated we'll store respective substring that created that hash

HOW TO GENERATE HASH Since from given constraints, we know DNA has only 4 characters we'll assign a number to those A=1 C=2 G=3 T=4

we'll also need a constant for calculation; A constant value should be greater than or equal to number of characters allowed. For my simplicity I'll take smallest possible value of constant (a) = 4

For a string ACTCT and k=2

H(AC) = H(A) + H(C)

H(AC) = 1 × 4¹ + 2 × 4⁰ = 4 + 2 = 6

now we'll use previously generated value to find H(CT)

H(C)= H(AC)- H(A)

H(C)= 6 - 1*4¹ = 2

H(CT)= H(C)+ H(T)

H(CT)= 2 + 4*4⁰= 6

No, NO this can't be right because we got same hash value for H(AC) and H(CT), On careful inspection of calculation I found we are removing previous hash and adding new hash but we are not adjusting their position we'll need to shift remaining bases by one position so hash can corresponds to new sliding window. We can do it by muliplying previous value by our base value a=4

H(CT)= (H(AC)- H(A)) * base + H(T)

H(CT)= (6 - 1 * 4¹) * 4 + 4 * 4⁰ H(CT)= 12

H(TC)=(H(CT)- H(C)) * base + H(C)

H(TC)= (12- 2 * 4¹) * 4 + 2 * 4⁰ H(TC)= 18

similarly H(CT) = 12

Since H(CT) comes equal both the time it means our Hashing is working properly now

function repeatedDNS(s, k) {
    let numbers = [];
    let obj = { A: 1, C: 2, G: 3, T: 4 };
    let base = 4;
    let hash = 0;
    let hashSet = new Set();
    let result = new Set();

    for (let i = 0; i < s.length; i++) {
        numbers.push(obj[s[i]]);
    }

    for (let i = 0; i < k; i++) {
        hash += numbers[i] * Math.pow(base, k - i - 1);
    }
    hashSet.add(hash);

    for (let start = 1; start <= s.length - k; start++) {
        let previousHash = hash;
        hash = (previousHash - numbers[start - 1] * Math.pow(base, k - 1)) * base + numbers[start + k - 1];

        if (hashSet.has(hash)) {
            result.add(s.slice(start, start + k));
        } else {
            hashSet.add(hash);
        }
    }

    return result;
}

console.log(repeatedDNS('AGACCTAGAC', 3));

Complexity Time:O(N) Space:O(Nk) worse case