Leetcode-76- minimum covering substring

subject

Ideas

1. shock , It was sliding window again
2. Will the required letters exist hashMap Inside , Maintain with sliding window , See the code , Too lazy to write. .

Code

class Solution {
    
    public String minWindow(String s, String t) {
    
                // take t Chinese character addition hash surface 
        LinkedHashMap<Character,Integer> m1 = new LinkedHashMap();
        for(int i=0;i<t.length();i++){
    
            // Judge first whether there is value 
            if(m1.containsKey(t.charAt(i))){
    
                m1.put(t.charAt(i),1+m1.get(t.charAt(i)));
            }else m1.put(t.charAt(i),1);
        }
        // How many characters are needed in total 
        int needCount = t.length();
        // Start in s Slide up the window   use LR maintain   At first L=0 R=0
        int L=0,R=0;
        int ansL=0,ansR=0;
        while (L<=s.length()){
    
            while(needCount!=0){
     //R Slide right 
                if(R>=s.length()) break;
                // Record the current R The letter of 
                char c = s.charAt(R);
                if(m1.containsKey(c)){
    
                    // Get current value value If less than or equal to 0  Explanation is not necessary   If it is greater than 0  explain needcount Sure --
                    int value = m1.get(c);
                    if(value>0) needCount--;
                    m1.put(c,value-1);
                }else m1.put(c,-1); // Otherwise it is absolutely not important 
                R++;

            }
            // If you go here, it means that the current string already contains all   You can begin to L Slide right to eliminate unnecessary elements 
            while(true){
     // The premise to jump out is to encounter letters that cannot be deleted   I met +1 Will be greater than 0 The elements of   Just jump out 
                // If you come here needCount Greater than 0  explain R Has come to the end   You can no longer perform the following operations 
                if(needCount>0) break;
                char c = s.charAt(L);
                //m1 This must include c
                int value = m1.get(c);
                if(value+1>0) break;
                else {
    
                    L++;
                    m1.put(c,value+1);
                }
            }
            if(needCount>0) break;
            // It means that the sliding window has been found   Record length 
            if((ansL==0 && ansR==0 )||(ansR-ansL>R-L)){
    
                ansL = L;
                ansR = R;
            }
            // Ready for the next cycle   Give Way L Move right 
            char c = s.charAt(L);
            int value = m1.get(c);
            L++;
            m1.put(c,value+1);
            needCount++;
        }
        return s.substring(ansL,ansR);
    }
}