Complete Substring!

Posted: 28 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two strings ‘S1’ and ‘S2’. Your task is to find the smallest substring of ‘S1’ which contains all the characters of ‘S2’. The characters of ‘S2’ need not be present in the same order in S1. That is, we need a substring that contains all characters of ‘S2’ irrespective of the order.

A substring is a contiguous sequence of characters within a string.

Example

Let ‘S1’ be “ABBCD” and ‘S2’ be “ABC”, so the smallest substring of ‘S1’ which contains all the characters of S1 is “ABBA”.
Input format :
The first line contains a single integer T representing the number of test cases.

The first line of each test case contains the string ‘S1’.

The first line of each test case contains the string ‘S2’.
Output format :
For each test case, print the smallest substring of S1 which contains all the characters of S2. Print an empty ( “” ) string if no substring of S1 contains all the characters of S2.

The output of each test case should be printed in a separate line.
Note
You are not required to print anything, it has already been taken care of. Just implement the function.    
Constraints :
1 <= T <= 10
1 <= |S1| <= 10^4
1 <= |S2| <= 10^4

The strings S1 and S2 contain only uppercase Latin alphabets.

Where |S| represents the length of string S.

Time Limit: 1sec
Approach 1

Generate all substrings of S1 and check which sub-strings contain all characters of S2. Return the smallest substring among them.

 

 

Algorithm:-

 

  1. If ‘S1’ does not contain all the characters of ‘S2’ return “”.
  2. Initialize answer with string ‘S1’.
  3. Run a for-loop from 0 to ‘N’ (let’s say the iterator be i).
    1. Run a nested for-loop from i to ‘N’(let’s say the iterator be j).
      1. Check if the substring of ‘S1’ from index i to j contains all the characters of ‘S2’.
      2. If the substring of ‘S1’ from index i to j contains all the characters of ‘S2’ then update the answer if the length of the previous answer was greater.
  4. Return answer.
Try Problem