Hi,
I just did the Sliding Window - Solution Review: Problem Challenge 1. I feel like the given solution could be further optimized to be O(N) with this code:
Python code:
def find_permutation(input_str, pattern):
window_start = 0
remaining_string = pattern
for window_end in range(len(input_str)):
right_char = input_str[window_end]
# check remaining_string and update
if right_char in remaining_string:
remaining_string = remaining_string.replace(right_char, '', 1)
# update window start, and add it to remaining_string
else:
left_char = input_str[window_start]
if left_char in pattern:
remaining_string += left_char
window_start += 1
if remaining_string == '':
return True
return False
Javascript code:
const find_permutation = function(str, pattern) {
let window_start = 0,
remaining_chars = pattern;
for (let window_end = 0; window_end < str.length; window_end++){
// get the right char
const right_char = str[window_end];
// if right char in remaining, replace it with ""
if (remaining_chars.includes(right_char)) remaining_chars = remaining_chars.replace(right_char, "");
// else add left char back to remaining, update window start
else {
const left_char = str[window_start++];
if (pattern.includes(left_char)) remaining_chars += left_char;
}
// if remaining is "", return true
if (remaining_chars == "") return true;
}
return false;
};
Am I missing something? What are the reasons why I would prefer the solution provided using a Map and with a complexity of O(M+N) instead of the above?
Thanks in advance!