Complete Substring!

PROBLEM STATEMENT

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:-

If ‘S1’ does not contain all the characters of ‘S2’ return “”.
Initialize answer with string ‘S1’.
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.
Return answer.

Try Problem

Approach 2

Initialize two-pointers and keep adjusting the two-pointers such that the window between the two-pointers contains all the characters of S2. Take the smallest window among such windows.

Algorithm:-

First check if ‘S1’ contains all the characters of ‘S2’, return “”.
Initialize answer with string ‘S1’.
Initialize a map FREQ to store the occurrence of characters of ‘S2’.
Store the frequency of all the characters in ‘S2’ and store the number of distinct characters in ‘S2’ in a variable named COUNT.
Initialize two pointers ST and END and initialize them with 0.
Run a while loop till end is less than |S1|.
1. Increment the FREQ of S1[END] by 1.
2. If the frequency of S1[END] is greater than the frequency of S1[END] in S2, increment count by 1.
3. If COUNT is equal to the length of the characters in S2 this means a window is found.
4. If such a window is found, try to minimize it by removing extra characters from the beginning of the current window by deleting one character from first and decrement the frequency of S1[ST] by 1.
5. Check if the frequency of S1[ST] is greater than the frequency of S1[ST] in S2.
6. If yes then a new smaller window is found, so update the answer if the length of the previous answer was greater.
7. Increment st by 1.
Return answer.

Try Problem