educative.io

Educative

Looking to findout space and time complexity of my solution to this problem

const find_permutation = function(str, pattern) {
let windowStart =0;
for(let windowEnd =0; windowEnd < str.length; windowEnd ++){
//only need to check if the window is a permutation of the pattern if they are the same length.
if(windowEnd - windowStart +1 === pattern.length){
let permutation = true;
//put the possible permutation within a string for futher manupulation
let tempString = str.slice(windowStart,windowEnd+1);
for(let char of tempString){
if(!pattern.includes(char)){
permutation = false
break;
}
}
if(permutation === true){
return true;
}
windowStart ++;
}
}
return false;
};

would this be a timecomplexty of O(n + m)? and a space complexity of O(N)?

Yes @Alex_Pappa. Considering n is the length of the pattern and m is the length of the string, your solution has a time complexity of O(n + m) and space complexity of O(n).

1 Like