Smallest Window Contains Pattern
Programming Interview
Hard
4 views
Problem Description
You get {x}. Compute the length of smallest substring of s that contains all characters of p with at least same counts. If not possible output 0.
Input Format
Two lines: s then p.
Output Format
One integer minLen or 0.
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2:
sys.exit(0)
s=lines[0].strip()
p=lines[1].strip()
need={}
for ch in p:
need[ch]=need.get(ch,0)+1
have={}
required=len(need)
formed=0
l=0
best=len(s)+1
for r,ch in enumerate(s):
have[ch]=have.get(ch,0)+1
if ch in need and have[ch]==need[ch]:
formed+=1
while formed==required and l<=r:
ln=r-l+1
if ln<best:
best=ln
leftc=s[l]
have[leftc]-=1
if leftc in need and have[leftc]<need[leftc]:
formed-=1
l+=1
sys.stdout.write('0' if best==len(s)+1 else str(best))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!