187. Repeated DNA Sequences

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

Solution

/** * @param {string} s * @return {string[]} */ var findRepeatedDnaSequences = function(s) { var res = []; var map = {}; for (var i = 0; i <= s.length - 10; i++) { var str = s.slice(i, i + 10); var num = map[str]; if (num === -1) continue; if (num === 1) { map[str] = -1; res.push(str); continue; } map[str] = 1; } return res; }; 

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).