Minimum Window Substring
HardPractice library · +30 XPsliding windowtwo pointersstrings
Given a string s and a string t, find the shortest contiguous substring of s that contains every character of t including duplicates (if t has two a, the window needs at least two a).
If several windows have the shortest length, print the one that starts earliest. If no window exists print -1.
Input
Line 1: s
Line 2: t
Output
The shortest window, or -1.
Constraints
- 1 <= |t| <= |s| <= 200000
sandtcontain only lowercase letters
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
adobecodebanc abc
Output
banc
The shortest window is "banc".
Example 2
Input
a a
Output
a
Hints
Similar problems
- Longest Subarray with Distinct ElementsHard
- Longest Subarray with Bounded DifferenceMedium
- Count Pairs with Specific SumEasy
- Longest Subarray with At Most K Distinct ElementsMedium
- Optimal Training ScheduleMedium
- Longest Sorted SubsegmentMedium
More topics: Strings problems, Two Pointers problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
adobecodebanc abc
Example 2 input
a a