import java.util.*;
import java.util.stream.Collectors;
public class Test{
public static List<String> findRepeatedSequences(String s, int k) {
HashMap<String, Integer> cache = new HashMap<>();
for (int end = 0, start = 0; end < s.length(); end++) {
if (end - start + 1 >=k) {
cache.put(s.substring(start, end+1), cache.getOrDefault(s.substring(start, end+1), 0) + 1);
start++;
}
}
return cache
.entrySet()
.stream()
.filter(entry -> entry.getValue() > 1)
.map(Map.Entry::getKey)
.collect(Collectors.toCollection(LinkedList::new));
}
public static void main(String[] args) {
assert findRepeatedSequences("AGCTGAAAGCTTAGCTG", 5).equals(List.of("AGCTG"));
assert findRepeatedSequences("AGAGCTCCAGAGCTTG", 6).equals(List.of("AGAGCT"));
assert findRepeatedSequences("ATATATATATATATAT", 6).equals(List.of("ATATAT", "TATATA"));
}
}
Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Repeated DNA Sequences - Grokking Coding Interview Patterns in Java
