Given two strings S and P. Find the smallest window in the string S consisting of all the characters(including duplicates) of the string P. Return "-1" in case there is no such window present. In case there are multiple such windows of same length, return the one with the least starting index.
Note : All characters are in Lowercase alphabets.
Example 1:
Input:
S = "timetopractice"
P = "toc"
Output:
toprac
Explanation: "toprac" is the smallest
substring in which "toc" can be found.
Example 2:
Input:
S = "zoomlazapzo"
P = "oza"
Output:
apzo
Explanation: "apzo" is the smallest
substring in which "oza" can be found.
Your Task:
You don't need to read input or print anything. Your task is to complete the function smallestWindow() which takes two string S and P as input paramters and returns the smallest window in string S having all the characters of the string P. In case there are multiple such windows of same length, return the one with the least starting index.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(n) n = len(p) O
Constraints:
1 ≤ |S|, |P| ≤ 10^{5}

见题面

见题面