Find Distinct Repeated Ten-Base DNA Windows
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return every distinct length-10 substring that occurs more than once in the DNA string `s`. Overlapping occurrences count. Include a repeated sequence once, regardless of how many times it occurs. Results may be in any order.
```cpp
vector<string> findRepeatedDnaSequences(string s);
```
### Examples
```text
Input: s = "ACACACACACACA"
One valid output: ["ACACACACAC","CACACACACA"]
```
```text
Input: s = "AGTC"
Output: []
```
### Constraints & Assumptions
- Length is between 1 and 100000.
- Each character is A, C, G, or T.
- Search contiguous substrings of exactly ten characters.
### What a Strong Answer Covers
- All distinct repeated windows, including overlapping occurrences.
- No output for strings shorter than ten and no duplicate result entries.
- Time and storage accounting for the fixed window length.
### Follow-up Questions
- Does an occurrence overlapping another one still count?
- How many times should one sequence be returned after three occurrences?
Overview: Find all distinct repeated ten-base DNA windows, including overlapping occurrences, without imposing result order.
