Untitled
unknown
plain_text
2 years ago
1.8 kB
5
Indexable
class Solution { public String minWindow(String s, String t) { int len1 = s.length(); int len2 = t.length(); if(len1==0 || len2==0){ return ""; } int start = 0; int windowLength = -1; int end = 0; HashMap<Character, Integer> map2 = new HashMap<Character, Integer>(); for(int i=0; i<len2; i++){ char c = t.charAt(i); map2.put(c, map2.getOrDefault(c, 0)+1); } int required = map2.size(); int formed = 0; int left = 0; HashMap<Character, Integer> map1 = new HashMap<Character, Integer>(); for(int right=0; right<len1; right++){ char c = s.charAt(right); map1.put(c, map1.getOrDefault(c, 0)+1); if(map2.containsKey(c) && map1.get(c)==map2.get(c)){ formed++; } while(left<=right && formed==required){ int currMin = right - left + 1; if((windowLength==-1)||(windowLength>currMin)){ windowLength = currMin; System.out.println(windowLength); start = left; end = right; } char leftChar = s.charAt(left); if(map1.containsKey(leftChar)){ map1.put(leftChar, map1.get(leftChar)-1); } if(map2.containsKey(leftChar) && map1.get(leftChar)<map2.get(leftChar)){ formed--; } left++; } } if(windowLength==-1){ return ""; } return s.substring(start, end+1); } }
Editor is loading...