Last Updated: 4 Mar, 2021

# Minimum Window Substring

Hard
+3 more companies

## Problem statement

#### You are given two strings ‘A’ and ‘B’. Your task is to return a substring ‘S’ of ‘A’ such that the following conditions hold true :

``````• You can make ‘B’ from ‘S’ by removing some characters and rearranging some characters zero or more times.

• Length of ‘S’ must be as minimum as possible.
``````

#### Note :

``````Testcases are generated such that a substring always exists and is unique.
``````

#### Example :

``````A = ninjas, B = sin

All possible substrings with which 'B' can be created are
"ninjas", "injas".

Hence the substring with minimum length is "injas".
``````

#### Input Format :

``````The first line contains two space-separated strings ‘A’ and ‘B’.
``````

#### Output Format :

``````Print the substring with minimum length.
``````

#### Note :

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````

## Approaches

### 01 Approach

The idea here is to generate all possible substrings of “A” and check if it contains all characters of “B” or not.

#### Algorithm :

• Declare a variable to store the minimum length of the required substring and another to store the starting index, say, ‘answer’ and ‘startignIndex’. Initialize it with the length of string ‘A’ + 1 and 0 respectively.
• Declare a map say ‘count’ and store the frequency of all characters of ‘B’ in it.
• Generate all substrings of ‘A’ by running two nested loops.
• Say the current substring of ‘A’ be ‘current’.
• Check if ‘current’ contains all characters of ‘B’. This can be done by counting frequency of all characters of ‘current’ in a map, say, ‘countCurrent’.
• If all characters in ‘count’ map have frequency less than equal to ‘countCurrent’ then update the answer with a minimum of the length of ‘current’ and value of ‘answer’ and also vale of ‘startingIndex’ respectively and then break.
• If ‘answer’ equals to length of string ‘A’ + 1 then return -1, else return ‘answer’.