Find all length-10 DNA substrings that appear more than once in a string.
Given a DNA string consisting of the characters A, C, G, and T, return every contiguous substring of length 10 that occurs at least twice in the string. Each repeated sequence should appear once in the answer, even if it occurs many times.
A practical solution should avoid comparing every substring with every other substring when the input is large.
Input Format
- A single string
scontaining onlyA,C,G, andT. - The task is to examine all substrings of length
10.
Output Format
- Return a list of all distinct length-10 substrings that appear more than once in
s. - The order of the returned substrings does not matter.
Constraints
1 <= |s|- Only the characters
A,C,G, andTappear ins. - The target substring length is fixed at
10. - Each repeated substring should be included at most once in the output.
Example 1
Input
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output
["AAAAACCCCC","CCCCCAAAAA"]
Explanation
The substrings AAAAACCCCC and CCCCCAAAAA each appear more than once.
Example 2
Input
s = "AAAAAAAAAAAAA"
Output
["AAAAAAAAAA"]
Explanation
The length-10 substring AAAAAAAAAA appears multiple times, but it should only be returned once.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.