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