Smallest window in a string containing all the characters of another string

JavaView on GFG

Problem Overview

Same as minimum window substring.

Intuition

Same as minimum window substring. Sliding window approach.

Algorithm

1Frequency map of pattern. Two pointers. Expand right: update counts. When all covered: contract left. Update answer.

Common Pitfalls

• Identical to LC 76. The longer problem name is the same problem.

Smallest window in a string containing all the characters of another string.java

Java

// Approach: Sliding window. Expand right until all pattern chars found, then shrink left to minimize.
// Time: O(n + m) Space: O(1)
class Solution {
    // Function to find the smallest window in the string s consisting
    // of all the characters of string p.
    public static String smallestWindow(String s, String p) {
        int[] freq = new int[26];
        int[] store = new int[26];

        for (char ch : p.toCharArray()) {
            freq[ch - 'a']++;
            store[ch - 'a']++;
        }

        int start = 0;
        int end = 0;
        int min = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int len = 0;

        while (j < s.length()) {
            if (store[s.charAt(j) - 'a'] > 0) {
                freq[s.charAt(j) - 'a']--;
                if (freq[s.charAt(j) - 'a'] >= 0)
                    ++len;
            }

            while (len == p.length()) {
                if (j - i + 1 < min) {
                    start = i;
                    end = j;
                    min = j - i + 1;
                }
                if (store[s.charAt(i) - 'a'] > 0) {
                    freq[s.charAt(i) - 'a']++;
                    if (freq[s.charAt(i) - 'a'] > 0)
                        --len;
                }
                ++i;
            }
            ++j;
        }
        return (min == Integer.MAX_VALUE) ? "-1" : s.substring(start, end + 1);
    }
}

Was this solution helpful?