Sliding window

Question 1

Given a string, s, that represents a DNA subsequence, and a number
𝑘
k
, return all the contiguous subsequences (substrings) of length
𝑘
k
that occur more than once in the string. The order of the returned subsequences does not matter. If no repeated substring is found, the function should return an empty set.

Answer 1

T O(nk)
S O(nk)

function findRepeatedSequences(s, k) {
    const results = new Set();
    const cache = new Map();
    let left = 0;

    while(left+k <= s.length){
        const substring = s.substring(left, left+k);

        if(cache.has(substring)){
            results.add(substring);
        }else{
            cache.set(substring, true);
        }

        left++;
    }
   
    
    return results;
}

for optimised solution use rolling hash for comparing strings