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.
Overview: This question evaluates algorithmic problem-solving skills in string processing, focusing on managing character multiplicities and correctness when identifying constrained substrings.
Read the full Google Software Engineer interview experience this question came from
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.
Hints
- Expand with the right pointer, then shrink while all required characters are covered.
Community answers
Answer by lalhemal11
if (s.length() == 0 || t.length() == 0) {
return "";
}
// Dictionary which keeps a count of all the unique characters in t.
Map dictT = new HashMap();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
// Number of unique characters in t, which need to be present in the desired window.
int required = dictT.size();
// Left and Right pointer
int l = 0, r = 0;
// formed is used to keep track of how many unique characters in t
// are present in the current window in its desired frequency.
// e.g. if t is "AABC" then the window must have two A's, one B and one C.
// Thus formed would be = 3 when all these conditions are met.
int formed = 0;
// Dictionary which keeps a count of all the unique characters in the current window.
Map windowCounts = new HashMap<
Character,
Integer
();
// ans list of the form (window length, left, right)
int[] ans = { -1, 0, 0 };
while (r < s.length()) {
// Add one character from the right to the window
char c = s.charAt(r);
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
// If the frequency of the current character added equals to the
// desired count in t then increment the formed count by 1.
if (
dictT.containsKey(c) &&
windowCounts.get(c).intValue() == dictT.get(c).intValue()
) {
formed++;
}
// Try and contract the window till the point where it ceases to be 'desirable'.
while (l <= r && formed == required) {
c = s.charAt(l);
// Save the smallest win