Smallest Window Containing All Characters

hard

Acceptance: 38%

StringsSliding Window

Two strings are given: a text string and a pattern string. Find the shortest contiguous portion of the text that contains every character of the pattern, accounting for multiplicities. If the pattern has a character appearing twice, the window must include at least two occurrences. Return the shortest such window, or an empty string if none exists.

Examples

Example 1:

Input:text = "adobecodebanc", pattern = "abc"

Output:"banc"

Explanation: The window 'banc' starting at index 9 includes 'a', 'b', and 'c', and no shorter window contains all three.

Example 2:

Input:text = "xyz", pattern = "xxyy"

Output:""

Explanation: The pattern requires two x's and two y's, but the text has only one of each.

Hints

import java.util.*;

class Solution {
    public String smallestWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        int left = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.merge(c, 1, Integer::sum);
            if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) valid++;
            while (valid == need.size()) {
                if (right - left + 1 < minLen) {
                    start = left;
                    minLen = right - left + 1;
                }
                char d = s.charAt(left);
                if (need.containsKey(d) && window.get(d).intValue() == need.get(d).intValue()) valid--;
                window.merge(d, -1, Integer::sum);
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

Time complexityO(n)

Space complexityO(n)

Smallest Window Containing All Characters

Examples

Hints

Related Problems