Leetcode–Minimum Window Substring

The Problem:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Notes:

  1. To count occurrence of characters, instead of using a hash map, can use an int array of 256
  2. Two pointer method with one point to end and one point to start. Pointer advance condition: move end forward till finds one window, then move start forward till the window no longer valid, then move end forward to find another valid window

Java Solution:

public class Solution {
    public String minWindow(String S, String T) {
        int[] tArr = new int[256];
        for(int i = 0; i < T.length(); i++){
            tArr[T.charAt(i)]++;
        }
        int [] sArr = new int[256];
        int match = 0;
        String min = "";
        int start = 0;
        for(int end = 0; end < S.length(); end++){
            if(tArr[S.charAt(end)] > sArr[S.charAt(end)]){
                match++;
            }
            sArr[S.charAt(end)]++;
            if(match==T.length()){
                 //--!!!--condition is > not >=, so moving start won't invalid the window
                while(sArr[S.charAt(start)] > tArr[S.charAt(start)]){
                    sArr[S.charAt(start)]--;
                    start++;
                   
                }
                
                if(min.length()==0 ||  min.length() > end-start+1){
                    min = S.substring(start, end+1);
                }
                // !!!----dont forget to remove effect of current start before start increase
                sArr[S.charAt(start)]--;
                start++;
                match--;
            }
            
        }
        return min;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s