content: package Sliding_Window;
  
  // Problem Statement: Smallest Window containing Substring (hard)
  // LeetCode Question: 76. Minimum Window Substring
  
  import java.util.HashMap;
  import java.util.Map;
  
  public class Problem_9_SmallestWindowContainingSubstring {
      public String findSubstring(String str, String pattern) {
          int windowStart = 0, matched = 0, minLength = str.length() + 1, subStrStart = 0;
          Map<Character, Integer> charFrequencyMap = new HashMap<>();
          for(char chr : pattern.toCharArray()){
              charFrequencyMap.put(chr, charFrequencyMap.getOrDefault(chr, 0) + 1);
          }
          for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
              char rightChar = str.charAt(windowEnd);
              if (charFrequencyMap.containsKey(rightChar)) {
                  charFrequencyMap.put(rightChar, charFrequencyMap.get(rightChar) - 1);
                  if (charFrequencyMap.get(rightChar) >= 0) {
                      matched++;
                  }
              }
              while (matched == pattern.length()) {
                  if (minLength > windowEnd - windowStart + 1) {
                      minLength = windowEnd - windowStart + 1;
                      subStrStart = windowStart;
                  }
                  char leftChar = str.charAt(windowStart++);
                  if (charFrequencyMap.containsKey(leftChar)) {
                      if (charFrequencyMap.get(leftChar) == 0) {
                          matched--;
                      }
                      charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) + 1);
                  }
              }
          }
          return minLength > str.length() ? "" : str.substring(subStrStart, subStrStart + minLength);
      }
  }
  