You are given alphanumeric strings, *s* and *t*. Find the minimum window (substring) in *s *that contains all the characters of *t*.

Input:

AYZABOBECODXBANC

ABC

Output: BANC

The minimum window is "BANC," which contains all letters, A, B, and C, from the second string. There is no window smaller than “BANC.”

Input:

BACRDESDFBAER

BAR

Output: BACR

Here, we can see that there are two smallest windows — “BACR” and “BAER.” However, the output is “BACR” because it is the leftmost window.

Input Parameters: There are two arguments in the input — a string named *s *and a string named *t*.

Output: Return a string result, which is the minimum window (substring) in string *s* that contains all characters of string *t*. If no such window exists, then return “-1” (string). If there are multiple minimum windows of the same length, then return the leftmost window.

**Constraints:**

- 1 <= length(s) <= 100000
- 1 <= length(t) <= 100000

**Solutions 1: Brute Force (brute_force_solution.java)**

This is a brute force approach. We check whether each substring of string *s* is a valid window or not. If we find it to be a valid window, we update our result accordingly.

*O(n^3), where n is the length of string s*

We are checking for all substrings, and there are O(n^2) substrings. We take O(n) time to check whether the particular substring can be a valid window. So total complexity is O(n^3).

*O(1)*

We create frequency arrays of size O(128) to count the occurrence of each character present in strings *t *and *s*. So overall complexity is O(1).

*O(n+m) where n is the length of string s and m is the length of string t*

It will take O(n+m) for storing input, as we are storing two strings of length n and length m. The auxiliary space used is O(1). Hence, the total complexity will be O(n+m).

**Note:** We could use an array of length 62 (with some mapping) instead of 128, but this is a general solution, which works for an input string containing any ASCII characters.

In this approach, we create an array named *frequency *to keep a count of occurrences of each character in string *t *[O(length of t)]. Now, we start traversing the string *s* and keep a variable *cnt,* which increases whenever we encounter a character present in string *t*.

When the value of count reaches the length of *t*, this substring contains all the characters present in string *t*. We try removing extra characters as well as unwanted characters from the beginning of the obtained string. The resultant string is checked to see if it is a minimum window, and the answer is updated accordingly.

This algorithm uses the two-pointer method, which is widely used in solving various problems.

*O(n), where n is the length of string s*

Since each character of string *s* is traversed at most twice, the algorithm’s time complexity is O(n) + O(m).

O(1)

We are creating two frequency arrays, each of size 128, which use extra space O(128) + O(128). Hence, the auxiliary space used is O(1).

*O(n+m), where n is the length of string s and m is the length of string t*

It will take O(n+m) for storing input, as we are storing two strings of length *n* and length *m, *and the auxiliary space used is O(1). Hence, the total complexity will be O(n+m).