Java Easy Solution using Sliding Window Concept


  • 0
    K

    I keep on adding characters in the window until it contains all the characters present in the string t. Once the window contain all the characters, I start shrinking it until the size is one less than size of string t.

    Example:
    S = "ADOBECODEBANC"
    T = "ABC"

    start of window =0, end=0;
    when end is at index 5, the String is ADOBEC which is min substring(length=6) until this index. res= 6.
    Now I start shrinking it until it has one less character contained in string T. Thus the new start now becomes 1.

    The size again becomes equal to string T's size when it reaches index 10. As the new substring length(10) is greater than previous res length, thus result size remains unchanged.

    Now again we shrink the window and when the new start index becomes 6.

    Now finally the size become equal to T's size when end comes at index 12. Now we start shrinking the window and calculate res at each point. when start reached 9 ,the new window length is less than the previous res length. Thus the new minimum substring becomes 4.(BANC)

    After increasing the start index further we cannot get all the characters of string T in the window. Thus the final answer is "BANC".

    public class Solution {
        public String minWindow(String s, String t) {
            int slen=s.length(),tlen=t.length();
            if(slen<tlen || slen==0 || tlen==0) return "";
            int[] count= new int[256];
            for(char c: t.toCharArray()) count[c]++;
            
            int start=0,end=0;
            int size=0;
            String res="";
            while(end<slen){
               if(count[s.charAt(end++)]-->0)
                   size++;     
                while(size==tlen){
                    if(res=="" || res.length()>end-start) res= s.substring(start,end);
                    if(count[s.charAt(start++)]++==0) size--;   
                }
            }
            return res;
            }
        }
    

  • 0
    P

    @kay_deep Difficult to understand!


  • 0
    K

    @penhaunt I have added some description. Hope it helps


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.