Skip to content

187. Repeated DNA Sequences 👍

  • Time: $O(10n) = O(n)$
  • Space: $O(10n) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  vector<string> findRepeatedDnaSequences(string s) {
    unordered_set<string> ans;
    unordered_set<string_view> seen;
    const string_view sv(s);

    for (int i = 0; i + 10 <= s.length(); ++i) {
      if (seen.contains(sv.substr(i, 10)))
        ans.insert(s.substr(i, 10));
      seen.insert(sv.substr(i, 10));
    }

    return {ans.begin(), ans.end()};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public List<String> findRepeatedDnaSequences(String s) {
    Set<String> ans = new HashSet<>();
    Set<String> seen = new HashSet<>();

    for (int i = 0; i + 10 <= s.length(); ++i) {
      final String seq = s.substring(i, i + 10);
      if (seen.contains(seq))
        ans.add(seq);
      seen.add(seq);
    }

    return new ArrayList<>(ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def findRepeatedDnaSequences(self, s: str) -> list[str]:
    ans = set()
    seen = set()

    for i in range(len(s) - 9):
      seq = s[i:i + 10]
      if seq in seen:
        ans.add(seq)
      seen.add(seq)

    return list(ans)