leetcode/MinSubstring.java at main · singhishan/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class MinSubstring{

    String minWindow(String s, String t) {
        String ans=" ";
        HashMap<Character,Integer> map2= new HashMap<>();
        for(int i=0;i<t.length();i++){
            char ch =t.charAt(i);
            map2.put(ch,map2.getOrDefault(ch,0)+1);
        }
        int matchCount=0;
        int dmct=t.length();
        HashMap<Character,Integer> map1 = new HashMap<>();
        int i=-1;
        int j=-1;

        while(true){
            boolean f1=false;
            boolean f2=false;

            //acquire
            while(i<s.length()-1 && matchCount<dmct){
                i++;
                char ch =s.charAt(i);
                map1.put(ch,map1.getOrDefault(ch,0)+1);

                if(map1.getOrDefault(ch,0) <= map2.getOrDefault(ch,0)){
                    matchCount++;
                }
                f1=true;

            }
            //release and collect answers
            while(j<i && matchCount==dmct){
                  String pans =s.substring(j+1,i+1);
                  if(ans.length()==0||pans.length()<ans.length()){
                      ans = pans;
                  }
                j++;
                char ch = s.charAt(j);
                if(map1.get(ch)==1){
                    map1.remove(ch);
                }else
                    map1.put(ch,map1.get(ch)-1);

                if(map1.getOrDefault(ch,0)<map2.getOrDefault(ch,0)){
                    matchCount--;
                }
                f2 =true;
            }
            if(f1==false && f2==false){
                break;
            }


        }


   return ans;
    }
}