Solve min window & animal conflicts
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 76. Minimum Window Substring: Given strings s and t, return the smallest substring of s that contains every character of t (including duplicates). Validate a hashmap where each key is an animal and its value is a list of animals that cannot share the same river bank; determine whether the exclusions are conflict-free.
https://leetcode.com/problems/minimum-window-substring/description/
Quick Answer: This question evaluates understanding of string algorithms, frequency-based sliding window techniques and hashmap/graph-based conflict detection, focusing on minimal substring search and modeling pairwise exclusions.
Given a string s, a string t, and an exclusion map exclusions where each key is an animal and its value is a list of animals that cannot share the same river bank, return a two-element list [min_window, conflict_free]. min_window is the smallest substring of s that contains every character of t (including duplicates); return an empty string if no such substring exists. conflict_free is true if the undirected graph formed by treating each exclusion as an edge is bipartite (i.e., the animals can be split into two banks so that no excluded pair is on the same bank), and false otherwise. A self-exclusion (an animal excluding itself) makes the configuration not conflict-free. Animals mentioned only in values are still considered nodes.
Constraints
- 0 <= len(s) <= 200000
- 0 <= len(t) <= 200000
- s and t consist of ASCII characters
- Number of distinct animals <= 100000
- Sum of lengths of all exclusion lists <= 200000
- Exclusions are treated as undirected edges
- Self-exclusion (animal listed as excluding itself) makes conflict_free = false
Solution
from collections import Counter, defaultdict, deque
def min_window_and_conflicts(s: str, t: str, exclusions: dict) -> list:
def min_window(s: str, t: str) -> str:
if not s or not t:
return ""
need = Counter(t)
required = len(need)
window = defaultdict(int)
formed = 0
l = 0
best_len = float('inf')
best_l = 0
best_r = -1
for r, ch in enumerate(s):
window[ch] += 1
if ch in need and window[ch] == need[ch]:
formed += 1
while l <= r and formed == required:
if r - l + 1 < best_len:
best_len = r - l + 1
best_l = l
best_r = r
left_ch = s[l]
window[left_ch] -= 1
if left_ch in need and window[left_ch] < need[left_ch]:
formed -= 1
l += 1
return "" if best_r == -1 else s[best_l:best_r+1]
def is_conflict_free(exclusions: dict) -> bool:
adj = {}
for u, vs in exclusions.items():
adj.setdefault(u, set())
for v in vs:
if v == u:
return False
adj.setdefault(v, set())
adj[u].add(v)
adj[v].add(u)
color = {}
for node in adj:
if node not in color:
dq = deque([node])
color[node] = 0
while dq:
u = dq.popleft()
for v in adj[u]:
if v == u:
return False
if v not in color:
color[v] = 1 - color[u]
dq.append(v)
elif color[v] == color[u]:
return False
return True
return [min_window(s, t), is_conflict_free(exclusions)]
Explanation
We solve two independent subproblems. 1) Minimum window substring: maintain a sliding window [l, r] over s and a frequency map of required characters from t. Expand r to include characters, tracking how many distinct character requirements are satisfied. When all are satisfied, shrink from l to find the smallest valid window, updating the best answer. This handles duplicates by exact count comparisons. 2) Conflict validation: build an undirected graph where an edge between two animals means they cannot share the same bank. The configuration is conflict-free iff the graph is bipartite. We check bipartiteness with BFS coloring across all components; any edge connecting same-colored vertices or any self-loop makes it invalid.
Time complexity: O(|s| + |t| + V + E). Space complexity: O(|t| + V + E).
Hints
- For the minimum window, use a sliding window with frequency counts: expand right until all required counts are met, then contract left to minimize.
- Treat exclusions as an undirected graph; check bipartiteness with BFS/DFS coloring across all components.
- Watch for self-loops (an animal excluding itself), which immediately make the graph not bipartite.