hardSliding WindowAI-applied~25 min
Find Length-10 Token Windows That Repeat
Scanning a long sequence over a 4-symbol alphabet, find all length-10 contiguous windows that appear more than once.
Problem
Given a string s consisting of characters from a small fixed alphabet (e.g. A, C, G, T), return all 10-character-long substrings that occur more than once in s. You may return the answer in any order.
Input
A string s.
Output
A list of the repeated 10-length substrings.
Constraints
- 1 <= s.length <= 10^5
- s consists of characters A, C, G, T.
- Return each repeated substring once.
Examples
Example 1
Input
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output
["AAAAACCCCC","CCCCCAAAAA"]
Both 10-length windows appear at least twice.
Example 2
Input
s = "AAAAAAAAAAAAA"
Output
["AAAAAAAAAA"]
The all-A window repeats.