import java.util.*;
public class FindRepeatedSequences{
public static Set<String> findRepeatedSequences(String s, int k) {
Map<String, Integer> sequenceCounter = new HashMap<>();
Set<String> result = new HashSet<>();
int length = s.length();
if (length <= k) return result;
int left = 0;
int right = k;
while (right < length) {
String substring = s.substring(left, right);
int occurrence = sequenceCounter.getOrDefault(substring, 0) + 1;
sequenceCounter.put(substring, occurrence);
left++;
right++;
}
for (String sequence : sequenceCounter.keySet()) {
int occurrence = sequenceCounter.get(sequence);
if (occurrence > 1) {
result.add(sequence);
}
}
return result;
}
}
The above solution passes all 11 test cases, but it will fail the following:
s=“AAACAAA” , k=3
This is because the above solution ends its while loop before checking the last substring, therefore missing the last sequence and returns an empty set. However, because the problem does not involve this edge case, the above solution will be accepted. This should use left = k - 1 and s.substring(left, right + 1)
import java.util.*;
public class FindRepeatedSequences{
public static Set findRepeatedSequences(String s, int k) {
Map<String, Integer> sequenceCounter = new HashMap<>();
Set<String> result = new HashSet<>();
int length = s.length();
if (length <= k) return result;
int left = 0;
int right = k - 1;
while (right < length) {
String substring = s.substring(left, right + 1);
int occurrence = sequenceCounter.getOrDefault(substring, 0) + 1;
sequenceCounter.put(substring, occurrence);
left++;
right++;
}
for (String sequence : sequenceCounter.keySet()) {
int occurrence = sequenceCounter.get(sequence);
if (occurrence > 1) {
result.add(sequence);
}
}
return result;
}
}
This testcase should be added.