Iam_Sandeep

Smallest distinct window

Jun 18th, 2022 (edited)
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.77 KB | None | 0 0
  1. '''
  2. Given a string 's'. The task is to find the smallest window length that contains all the characters of the given string at least one time.
  3. For eg. A = aabcbcdbca, then the result would be 4 as of the smallest window will be dbca.
  4. '''
  5. class Solution:
  6.     def findSubString(self, s):      
  7.         tar=set(s)
  8.         d={}
  9.         have,need=0,len(tar)
  10.         t={}
  11.         l=0
  12.         ans=float('inf')
  13.         for r in range(len(s)):
  14.             c=s[r]
  15.             d[c]=d.get(c,0)+1
  16.             if c in d and d[c]==1:
  17.                 have+=1
  18.             while have==need:
  19.                 ans=min(ans,r-l+1)
  20.                 d[s[l]]-=1
  21.                 if d[s[l]]==0 and s[l] in tar:
  22.                     have-=1
  23.                 l=l+1
  24.         return ans
  25.            
Add Comment
Please, Sign In to add comment