Katkat
Back

Find Shortest Covering Substring

Character.AISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window technique and hash maps to find the smallest window in a string that contains all characters of a target pattern.

Problem Statement

Given a string s and a string t, find the shortest substring in s that contains all the characters in t (including duplicates). If there are multiple such substrings of the same minimum length, return any one of them. If no such substring exists, return an empty string.

Function Signature

def shortest_covering_substring(s: str, t: str) -> str:

Constraints

  • 1 <= s.length <= 10^5
  • 1 <= t.length <= 10^4
  • s and t consist of English letters.

Examples

Example 1:

  • Input: s = "ADOBECODEBANC", t = "ABC"
  • Output: "BANC"
  • Explanation: The shortest substring that contains 'A', 'B', and 'C' is "BANC".

Example 2:

  • Input: s = "a", t = "aa"
  • Output: ""
  • Explanation: There is no substring in s that contains two 'a's.

Edge Cases

  • t is longer than s.
  • t contains characters not present in s.
  • s or t contains only one unique character.

Hints

Hint 1

Use a hash map (or frequency array) to keep track of the character counts required by `t`.

Hint 2

Maintain a sliding window defined by two pointers, `left` and `right`, and expand the `right` pointer until all characters from `t` are present in the current window.

Hint 3

Once the window is valid, move the `left` pointer to shrink it as much as possible while maintaining the 'valid' condition.

Follow-up questions

  • How would you modify your solution if the input strings contained Unicode characters?
  • What is the time and space complexity of your solution, and can you explain the worst-case scenario for the sliding window pointers?
  • How would you handle the case where the input string `s` is too large to fit into memory (e.g., a multi-gigabyte log file)?