Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 4 Mar, 2021

Minimum Window Substring

Hard
Asked in companies
JP MorganUberPaypal

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