# Complete Substring!

Posted: 28 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

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