educative.io

Solving task without hash function using sliding window approach - advantages and disadvantages

Courses
,
#1 
 public static List<String> findRepeatedSequences(String s, int k) {
        int windowStart = 0, windowEnd;
        StringBuilder sequenceBuilder = new StringBuilder();
        Set<String> set = new HashSet<>();
        Set<String> result = new HashSet<>();

        for (windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char chr = s.charAt(windowEnd);
            if (windowEnd - windowStart < k) {
                sequenceBuilder.append(chr);
            } else {
                String sequence = sequenceBuilder.toString();
                if (set.contains(sequence)) {
                    result.add(sequence);
                }

                set.add(sequence);
                sequenceBuilder.deleteCharAt(0);
                sequenceBuilder.append(chr);
                windowStart++;
            }
        }
        return new ArrayList<>(result);
}

Hello! What are the advantages and disadvantages of the above solution compared to the one proposed in the course? What is the advantage of the hash function solution over the above?

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

#2

Hi Andrey_Samoylov,

Your solution uses the toString() and deleteCharAt(0) methods which are both take O(n) time. So the overall complexity of your approach would become O(n * 2n) = O(2n^2).

The hashing solution on the other hand does not use these methods. It performs hashing in constant time. Hence, the overall complexity would be O(n).