Minimum Window Substring

Hard
0/120
Average time to solve is 15m
32 upvotes
Asked in companies
PayPalBarclaysUber

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".
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

fight it

Sample Output 1 :

ight

Explanation Of Sample Input 1 :

Given A = “fight” and B = “it” 

Consider the substring “ight” of A. 

We can remove g and h from it to get “it”.

We can also get "it" from "fight" but it is not the substring with minimum length.

Sample Input 2 :

coding cin

Sample Output 2 :

codin

Constraints :

1 <=  |A| = |B| <= 3000
Both A, B contain only lowercase English letters.

Where |A| and |B| are the length of strings.

Time Limit: 1 sec
Hint

Check all possible substrings.

Approaches (2)
Brute Force

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’.

 

Time Complexity

O( ( |A| ^ 2 ) + |A| + |B| ), where |A| is the length of the given string ‘A’ and |B| is the length of the given string ‘B’.

 

We are running two loops to generate all substring that takes O(|A| ^ 2) time. Also checking the validity of a substring takes O(26) time as both strings can contain at most 26 characters. O(26) is basically O(1). Also, our ‘count’ map takes O( |A| ) time and ‘countCurrent’ map takes O( |B| ) time to store frequencies of string ‘A’ and ‘B’ respectively.

So overall time complexity = O( ( |A| ^ 2 ) + |A| + |B| ).

Space Complexity

O(1).

 

We are using two maps that take O(26) space as there can be a maximum of 26 characters in the map. O(26) is basically O(1).

Code Solution
(100% EXP penalty)
Minimum Window Substring
Full screen
Console