Document Target Match and Shortest Window ## Problem Summary You are given: * A document string containing text (letters, numbers, punctuation). * A targets list of words to look for. The interv

Document Target Match and Shortest Window ## Problem Summary You are given: * A document string containing text (letters, numbers, punctuation). * A targets list of words to look for. The interview has three steps: 1. Check if all the target words exist in the document. 2. Count how many times each target word appears. 3. Find the shortest piece of text that contains all the target words.

Key Rule: targets do not have punctuation, but the document does. You must ignore punctuation when matching. * Example: The target "isnt" should match the word "isn't" in the document.

Input and Output Example

python document = "This is an example document. This document isn't very special." targets = ["document", "document", "isnt"]

Expected

result ```
python match = True count = { "document": 2, "isnt": 1, } sub_doc = "document. This document isn't"

## Step 1: Check for Missing Words ### Requirement Return `True` if every word in `targets` is found in the `document`. If a word is listed twice in `targets`, it must appear at least twice in the `document`.

**Solution**

**Approach** First, we need to "clean" or normalize the words. We convert everything to lowercase and remove symbols. This allows `"isn't"` to match `"isnt"`. Then we compare the counts: 1. Count the frequency of each word in `targets`. 2. Go through the `document`, clean each word, and count it if it is in our list. 3. Check if we found enough of every word.

python from collections import Counter def normalize_word(s: str) -> str: # Keep only letters and numbers, then convert to lowercase return "".join(ch.lower() for ch in s if ch.isalnum()) def coverage_match(document: str, targets: list[str]) -> bool: # Count what we need need = Counter(normalize_word(t) for t in targets) need.pop("", None) # Remove empty strings if they exist if not need:

return True have = Counter() for raw in document.split(): word = normalize_word(raw) # Only count words we actually look for if word in need: have[word] += 1 # Check if we have enough of every target word return all(have[w] >= c for w, c in need.items())

### Step 1 Complexity | Metric | Complexity | | --- | --- | | Time | O(n + m) | | Space | O(u) | `n = number of words in document`, `m = number of targets`, `u = unique target words`. ## Step 2: Count Word Frequency ### Requirement Return a count of how many times each target word appears in the document. * Use the cleaned (normalized) version of the word. * The output map should list each unique target word once.

**Solution**

**Approach** We use the same cleaning logic as Step 1. We simply iterate through the document and update the count for any word that is in our target list.

python from collections import Counter def target_counts(document: str, targets: list[str]) -> dict[str, int]: normalized_targets = [normalize_word(t) for t in targets] target_set = {t for t in normalized_targets if t} # Initialize counts to 0 counts = {t: 0 for t in target_set} for raw in document.split(): word = normalize_word(raw) if word in counts: counts[word] += 1 return counts

### Step 2 Complexity | Metric | Complexity | | --- | --- | | Time | O(n + m) | | Space | O(u) | ## Step 3: Find the Smallest Window ### Requirement Find the shortest substring in `document` that contains all the target words. * If you cannot find one,

**return** an empty string `""`. * Match words using the cleaning rules (ignore punctuation). * The output must be the **original text** (keep the punctuation and capital letters exactly as they were).

**Solution**

**Approach** We use the

**Sliding Window** technique. 1.

**Tokenize:** Break the document into a list. For every word, store the original text, the cleaned text, and its start/end position indices. 2.

**Expand:** Move a `right` pointer to include words in our window. 3.

**Shrink:** Once the window has all the required words, move the `left` pointer to make the window smaller. 4.

**Track Best:** Keep track of the smallest valid window seen so far. 5.

**Result:** Use the stored start/end indices to return the exact string from the original document.

python from collections import Counter, defaultdict def tokenize_with_spans(document: str) -> list[tuple[str, str, int, int]]: tokens: list[tuple[str, str, int, int]] = [] n = len(document) i = 0 while i < n: # Skip whitespace to find start of a word while i < n and document[i].isspace(): i += 1 if i >= n: break start = i # Find end of the word while i < n and not document[i].isspace(): i += 1 end = i raw = document[start:end] norm = normalize_word(raw) tokens.append((raw, norm, start, end))

return tokens def min_cover_sub_document(document: str, targets: list[str]) -> str: need = Counter(normalize_word(t) for t in targets) need.pop("", None) if not need:

return "" tokens = tokenize_with_spans(document) if not tokens:

return "" required_total = sum(need.values()) window = defaultdict(int) formed = 0 best_len = float("inf") best_range: tuple[int, int] | None = None left = 0 # Expand the window with 'right' pointer for right in range(len(tokens)): , norm_r, , _ = tokens[right] if norm_r in need: window[norm_r] += 1 if window[norm_r] <= need[norm_r]: formed += 1 # Shrink the window with 'left' pointer if valid while formed == required_total and left <= right: , , start_l, _ = tokens[left] , , , end_r = tokens[right] cur_len = end_r - start_l # Update best result if this window is smaller if cur_len < best_len: best_len = cur_len best_range = (start_l, end_r) , norm_l, _, _ = tokens[left] if norm_l in need: window[norm_l] -= 1 if window[norm_l] < need[norm_l]: formed -= 1 left += 1 if best_range is None:

return "" start, end = best_range return document[start:end]
```

Step 3 Complexity | Metric | Complexity | | --- | --- | | Time | O(n + m) | | Space | O(n + u) | n = number of document tokens, m = number of targets, u = unique target words. ### Extra Discussion * If the interviewer asks about matching many patterns in a long stream of characters (not separated by spaces), mention using a

Trie. * However, for this problem where we split by words (tokens), HashMaps combined with a Sliding Window are usually the best and simplest choice.