LeetCode Solution - Problem Repeated DNA Sequences

• 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:

Java:

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String substring = s.substring(i, i+10);
            map.put(substring, map.getOrDefault(substring, 0) + 1);
        }

        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> item : map.entrySet()) {
            if (item.getValue() > 1) {
                list.add(item.getKey());
            }
        }
        return list;
    }
}

Python:

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        n = len(s)
        cnt = defaultdict(int)
        for i in range(n - 9):
            cnt[s[i:i+10]] += 1
        
        ans = []
        for key, value in cnt.items():
            if value >= 2: # Found a string that occurs more than once
                ans.append(key)
        return ans