educative.io

Educative

Possible O(N) Solution

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!

I believe your solution will not work for the following case:
Str = “aacb”
Pattern = “abc”
Let me know if I am wrong.