CODEWITHSUNDEEP
python-3.xsetsliding-window
jay
jay

Reputation: 1463

Time complexity of checking whether a set is contained in another set

I am trying to implement the example of finding the shortest substring of a given string s containing the pattern char. My code is working fine, but my goal is to attain the time complexity of O(N) where N is length of s. Here is my code;

def shortest_subtstring(s,char):
#smallest substring containing char.use sliding window
start=0
d=defaultdict(int)
minimum=9999
for i in range(len(s)):
    d[s[i]]+=1
    #check whether all the characters from char has been visited.
    while set(char).issubset(set([j for j in d if d[j]>0])):
        #if yes, can we make it shorter

        length=i-start+1
        minimum=min(length,minimum)
        if length==minimum:
            s1=s[start:i+1]
        d[s[start]]-=1
        start+=1
return (minimum,s1)

My question is at the line;

 while set(char).issubset(set([j for j in d if d[j]>0]))

Each time I am checking whether all strings of char are saved in my dictionary or not, using the idea of is.subset. May I know how can I find the time complexity of this step in my code? Is it O(1) , which is true for checking wether an element exists in a set or not. Otherwise, the time complexity will be much greater than O(N). Help is appreciated.

Upvotes: 0

Views: 1068

Answers (1)

andreis11
andreis11

Reputation: 1141

Per docs s.issubset(t) is the equivalent of s <= t meaning that during the operation it will test if every element in s is in t.

Best scenario: if s is the first element of t -> O(1)

Worst case scenario: if s in the last element of t -> O(len(t))

That is for isubset. For the list comprehension :

j for j in d is O(n) for getting each key

if d[j]>0 is O(n) for comparing each value of dictionary d

Here you can find more info.

Upvotes: 1

Related Questions