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)]