76. Minimum Window Substring | LeetCode | Top Interview 150 | Coding Questions

Problem Link

https://leetcode.com/problems/minimum-window-substring/

---

Detailed Step-by-Step Explanation

https://leetcode.com/problems/minimum-window-substring/solutions/7463548/most-optimal-solution-ever-beats-200-has-7gg4

---

---

Solution

class Solution {
    public String minWindow(String s, String t) {

        HashMap<Character, Integer> freqMap = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        int uniqueCharCount = freqMap.size();
        int windowStart = 0;
        int windowEnd = 0;
        int minLen = Integer.MAX_VALUE;
        int startIndex = -1;

        while (windowEnd < s.length()) {
            char ch = s.charAt(windowEnd);

            if (freqMap.containsKey(ch)) {
                freqMap.put(ch, freqMap.get(ch) - 1);
                if (freqMap.get(ch) == 0) {
                    uniqueCharCount--;
                }
            }

            while (uniqueCharCount == 0) {
                int len = windowEnd - windowStart + 1;
                if (len < minLen) {
                    minLen = len;
                    startIndex = windowStart;
                }

                ch = s.charAt(windowStart);
                if (freqMap.containsKey(ch)) {
                    freqMap.put(ch, freqMap.get(ch) + 1);
                    if (freqMap.get(ch) > 0) {
                        uniqueCharCount++;
                    }
                }
                windowStart++;
            }

            windowEnd++;
        }

        return startIndex == -1 ? "" : s.substring(startIndex, startIndex + minLen);
    }
}