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.
Testcases are generated such that a substring always exists and is unique.
A = ninjas, B = sin All possible substrings with which 'B' can be created are "ninjas", "injas". Hence the substring with minimum length is "injas".
Given A = “fight” and B = “it” Consider the substring “ight” of A. We can remove g and h from it to get “it”. We can also get "it" from "fight" but it is not the substring with minimum length.
1 <= |A| = |B| <= 3000 Both A, B contain only lowercase English letters. Where |A| and |B| are the length of strings. Time Limit: 1 sec