educative.io

Educative

The solution is overkill, I think I have a much more simple solution

def find_permutation(string, target_string):

  target_string = ''.join(sorted(target_string))
  current_string = ''
  
  for char in string:
      
      # increase the window (equivalent to adding the next character to current string)
      current_string += char
      
      # start checking the window once the window size is size of target_string
      if len(current_string) == len(target_string):
          
          # sort the current string and check if it equals the target_string
          if ''.join(sorted(current_string)) == target_string:
              return True
          
          # shrink the window for next iteration (remove the leftmost character)
          current_string = current_string[1:]

  return False
1 Like

I think slicing in python is O(k) so that would make this solution O(n * k), I think.

1 Like

@simran is correct - taking a slice in python requires iterating over all elements in the slice, which is O(k). Also, you’re doing a sort which also adds to the runtime complexity.

Also, slicing only produces a shallow copy. So if you have sublists/dicts/any other mutable objects in the list you are slicing, any modifications you make to them in the slice (shallow copy) also affect the original list’s elements.

e.g.

list1 = [[1,2], [3,4]]
list2 = list1[0:1]
list2[0].append(5)
print(list1)

Output:
[[1, 2, 5], [3, 4]]
1 Like