https://leetcode.com/problems/repeated-dna-sequences

Let us just put all sequences of length 10 into list, then apply counter: count how many times each element is present and finally return elements with frequency more than 1.

Complexity: Time and space complexity is O(10n): ther will be O(n) substrings of length 10.

class Solution:
    def findRepeatedDnaSequences(self, s):
        Count = Counter(s[i-10:i] for i in range(10, len(s) + 1))
        return [key for key in Count if Count[key] > 1]

Remark When I saw this problem, my first idea was to use rolling hash, which potentially can give us O(n) instead of O(10n) complexity. However we need not only evaluate how many repeated substrings of length 10 we have, but also return them all. This potentially can spend O(n) time: imagine example: TT, where T is string of length n/2. Then if all substring in T are different, we have O(n/2) different substings, we need to return, which gives us O(5n) space complexity of output.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0187