Find minimum covering substring
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given two strings s and t, return the shortest contiguous substring of s that contains every character of t with at least the same multiplicities. If multiple answers exist, return any one of the shortest; if none exist, return an empty string. State and justify your algorithm, analyze time and space complexity, and implement the solution in your preferred language.
Quick Answer: This question evaluates algorithmic problem-solving skills in string processing, focusing on managing character multiplicities and correctness when identifying constrained substrings.
Return the shortest substring of s containing every character of t with multiplicity.
Constraints
- Characters are case-sensitive
Examples
Input: ('ADOBECODEBANC', 'ABC')
Expected Output: 'BANC'
Explanation: Classic minimum window.
Input: ('a', 'aa')
Expected Output: ''
Explanation: Impossible.
Input: ('aa', 'aa')
Expected Output: 'aa'
Explanation: Whole string.
Input: ('bba', 'ab')
Expected Output: 'ba'
Explanation: Left shrink after satisfying counts.
Hints
- Expand with the right pointer, then shrink while all required characters are covered.