Complete Substring!

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
17 upvotes
Asked in companies
FiservMakeMyTripMicrosoft

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
ABC
ABC
ACBBBCA
ABC
Sample Output 1
ABC
ACB
Explanation For Sample Output 1
In the first test case, the substring “ABC” is the smallest substring of S1 which contains all the characters of S2.

In the second test case, the substring “ACB” is the smallest substring of S1 which contains all the characters of S2. Note that the order of the alphabets does not matter in the substring.
Sample Input 2
2
ABBBB
ABC
EFGHIJKL
EL
Sample Output 2
EFGHIJKL
Hint

Check all substrings of S1.

Approaches (2)
Brute Force

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.
Time Complexity

O(|S1| * |S1| * |S2|), where |S| is the length of the string ‘S’.


 

We are iterating through every substring of S1, so there are |S1| * |S1| substrings in S1 and for every substring, we are calculating the frequency of every character in |S2|, so the overall Time complexity is O(|S1| * |S1| * |S2|), where |S| is the length of the string ‘S’.

Space Complexity

O(|S1|), where |S1| is the length of the string ‘S1’.

 

We are storing the substring which contains all the characters of ‘S2’ in the variable answer which can be of a maximum length of |S1|, so |S1| Space is used.

Code Solution
(100% EXP penalty)
Complete Substring!
Full screen
Console