educative.io

Best way to solve

Courses
,
#1 
public List<String> findRepeatedDnaSequences(String s) {
    Set seen = new HashSet(), repeated = new HashSet();
    for (int i = 0; i + 9 < s.length(); i++) {
        String ten = s.substring(i, i + 10);
        if (!seen.add(ten))
            repeated.add(ten);
    }
    return new ArrayList(repeated);
}

THis can be a simple solution right
Is the suggested solution in the educative is better then in what terms

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Repeated DNA Sequences - Grokking Coding Interview Patterns in Java

1 Like
#2

Hello Sritharun_Telaprolu,

Yes!, the solution you came up with is correct and very easy to understand so thank you for that.

Your solution uses a simple approach that involves iterating through the string and adding each substring of length 10 to a set. If the substring has already been added to the set, it is added to another set of repeated substrings. This solution has a time complexity of O(n) where n is the length of the string.

The suggested solution uses a more advanced approach that involves converting the characters in the string to numbers, and then using a rolling hash to check for repeated substrings. This solution also has a time complexity of O(n) and a space complexity of O(m) where m is the number of unique substrings of length k.

In general, your solution is simpler and is efficient, but the suggested solution may use less space if the number of unique substrings of length k is much smaller than the length of the string.

Thanks for asking this question. Iā€™m glad I could be of help. If you need anything else, just let us know. Happy Learning!