Minimum Window Substring

Hard

Python

def min_window(s,t):
    from collections import Counter
    need=Counter(t); missing=len(t); best=None; left=0
    for r,c in enumerate(s,1):
        if need[c]>0: missing-=1
        need[c]-=1
        if missing==0:
            while need[s[left]]<0: need[s[left]]+=1; left+=1
            if best is None or r-left<len(best): best=s[left:r]
            need[s[left]]+=1; missing+=1; left+=1
    return best or ''

Java

public String minWindow(String s,String t){
    int[] need=new int[128]; int missing=t.length();
    for(char c:t.toCharArray()) need[c]++;
    int best=-1,blen=Integer.MAX_VALUE,left=0;
    for(int r=0;r<s.length();r++){
        if(need[s.charAt(r)]-->0) missing--;
        while(missing==0){
            if(r-left+1<blen){blen=r-left+1;best=left;}
            if(++need[s.charAt(left++)]>0) missing++;
        }
    } return best<0?"":s.substring(best,best+blen);
}

Key Insight

Counter vs int[128] ASCII array. Java char as array index trick.

Python → Java Differences

Counter vs int[128]
char as array index ASCII trick
Sliding window minimum identical

Python

def min_window(s,t):
    from collections import Counter
    need=Counter(t); missing=len(t); best=None; left=0
    for r,c in enumerate(s,1):
        if need[c]>0: missing-=1
        need[c]-=1
        if missing==0:
            while need[s[left]]<0: need[s[left]]+=1; left+=1
            if best is None or r-left<len(best): best=s[left:r]
            need[s[left]]+=1; missing+=1; left+=1
    return best or ''

Java

public String minWindow(String s,String t){
    int[] need=new int[128]; int missing=t.length();
    for(char c:t.toCharArray()) need[c]++;
    int best=-1,blen=Integer.MAX_VALUE,left=0;
    for(int r=0;r<s.length();r++){
        if(need[s.charAt(r)]-->0) missing--;
        while(missing==0){
            if(r-left+1<blen){blen=r-left+1;best=left;}
            if(++need[s.charAt(left++)]>0) missing++;
        }
    } return best<0?"":s.substring(best,best+blen);
}

Algorithm Steps

1. Count needed
2. Expand right until valid
3. Shrink left while valid

← Previous All Strings Next →