Skip to main content

Repeated DNA Sequences

Problem statement​

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'.

My solution​

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    const map = new Map();
    let i = 0;
    let j = 0;
    const result = [];
    
    while (j < s.length) {
        if (j - i + 1 < 10) {
            j++
        } else if (j - i + 1 === 10) {
            const key = s.slice(i, j + 1);
            map.set(key, (map.get(key) || 0) + 1)
            
            i++;
            j++;
        }
    }
    
    // console.log(map)
    
    
    for (const [key, value] of map.entries()) {
        if (value > 1) {
            result.push(key)
        }
    }
    
    return result;
};