Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Sliding Window

Minimum Window Substring

Hard · Sliding Window · Asked at Meta, Amazon, Google, Microsoft, Uber

Find the shortest substring of s that contains every character of t, including duplicates. If several windows have the minimum length, print the leftmost one. If no window exists, print -1.

Input

First line: s. Second line: t. Both consist of English letters (upper and lower case).

Output

The minimum window, or -1.

Constraints

Expand the right end until the window covers t, then shrink from the left as long as it still covers t. Track how many required characters are still missing.

Example 1

Input

ADOBECODEBANC
ABC

Output

BANC

Example 2

Input

a
aa

Output

-1

Hints

  1. Count what t needs. Expand the right end of the window, and track how many required characters are still missing.
  2. When nothing is missing, the window is valid: record it if it is shorter, then shrink from the left while it stays valid.

Approach

need[c] = occurrences of c in t; missing = |t|. Move r over s: increment have[s[r]], and if that character was still needed (have ≤ need), decrement missing. While missing == 0, the window [l, r] covers t — update the answer (only when strictly shorter, so the leftmost window wins ties), then remove s[l], and if that makes a needed count drop below need, increment missing; advance l. Each index enters and leaves once.

Complexity: O(|s| + |t|) time · O(alphabet) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> need(128, 0), have(128, 0);
    for (char c : t) need[c]++;
    int missing = t.size(), l = 0, bestL = -1, bestLen = INT_MAX;
    for (int r = 0; r < (int)s.size(); r++) {
        if (++have[s[r]] <= need[s[r]]) missing--;
        while (missing == 0) {
            if (r - l + 1 < bestLen) bestLen = r - l + 1, bestL = l;
            if (--have[s[l]] < need[s[l]]) missing++;
            l++;
        }
    }
    if (bestL < 0) cout << -1 << "\n";
    else cout << s.substr(bestL, bestLen) << "\n";
    return 0;
}

Python solution

import sys

s, t = sys.stdin.read().split()[:2]
need, have = [0] * 128, [0] * 128
for c in t:
    need[ord(c)] += 1
missing, l, best = len(t), 0, None
for r, c in enumerate(s):
    have[ord(c)] += 1
    if have[ord(c)] <= need[ord(c)]:
        missing -= 1
    while missing == 0:
        if best is None or r - l + 1 < best[1] - best[0]:
            best = (l, r + 1)
        d = ord(s[l])
        have[d] -= 1
        if have[d] < need[d]:
            missing += 1
        l += 1
print(s[best[0] : best[1]] if best else -1)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(), t = sc.next();
        int[] need = new int[128], have = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int missing = t.length(), l = 0, bestL = -1, bestLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (++have[c] <= need[c]) missing--;
            while (missing == 0) {
                if (r - l + 1 < bestLen) {
                    bestLen = r - l + 1;
                    bestL = l;
                }
                char d = s.charAt(l++);
                if (--have[d] < need[d]) missing++;
            }
        }
        System.out.println(bestL < 0 ? "-1" : s.substring(bestL, bestL + bestLen));
    }
}

Solve Minimum Window Substring online · All practice problems