Dare2Solve
The task is to find all 10-letter-long sequences (substrings) that occur more than once in a given string. Each sequence should be returned as a list of strings. For example, given the string "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
, the repeated 10-letter sequences are "AAAAACCCCC"
and "CCCCCAAAAA"
.
The problem is about detecting repeating sequences within a string. We need to identify and list substrings of exactly 10 characters that appear more than once. The key challenge is efficiently tracking and comparing these substrings to find duplicates.
Handle Short Strings:
Initialize Data Structures:
Iterate Through the String:
Return Results:
O(n)
, where n
is the length of the input string. The algorithm processes each character of the string once and performs constant-time operations for each substring.
O(n)
, where n
is the length of the input string. Space is used for the map and result list, which store occurrences of substrings and repeated substrings respectively.
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> result;
if (s.length() < 10) return result; // Handle short strings
unordered_map<string, int> map;
for (int i = 0; i <= s.length() - 10; ++i) {
string substring = s.substr(i, 10);
if (map.count(substring)) {
if (map[substring] == 1) {
result.push_back(substring);
}
map[substring]++;
} else {
map[substring] = 1;
}
}
return result;
}
};
class Solution:
def findRepeatedDnaSequences(self, s: str) -> list[str]:
map = {}
result = []
for i in range(len(s) - 9):
substring = s[i:i + 10]
if substring in map:
if map[substring] == 1:
result.append(substring)
map[substring] += 1
else:
map[substring] = 1
return result
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Map<String, Integer> map = new HashMap<>();
List<String> result = new ArrayList<>();
for (int i = 0; i <= s.length() - 10; i++) {
String substring = s.substring(i, i + 10);
if (map.containsKey(substring)) {
if (map.get(substring) == 1) {
result.add(substring);
}
map.put(substring, map.get(substring) + 1);
} else {
map.put(substring, 1);
}
}
return result;
}
}
var findRepeatedDnaSequences = function (s) {
let map = new Map();
let result = [];
for (let i = 0; i <= s.length - 10; i++) {
let substring = s.substring(i, i + 10);
if (map.has(substring)) {
if (map.get(substring) === 1) {
result.push(substring);
}
map.set(substring, map.get(substring) + 1);
} else {
map.set(substring, 1);
}
}
return result;
};