Đề bài · xử lý chuỗi khó Python ·
Minimum window substring
Return the shortest substring of s that contains every character of t, counting repeats (if t has two "a", the window needs two "a"). If several windows are equally short, return the leftmost. Return "" if there is no such window or t is empty. s can be up to 200,000 characters long.
Khai báo hàm
def min_window(s: str, t: str) -> str:Ví dụ
min_window('ADOBECODEBANC', 'ABC') # -> 'BANC'
min_window('a', 'aa') # -> ''
min_window('a', 'a') # -> 'a'Kèm theo 8 test ẩn và 2 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1Anthropic Claude Opus 5.5đã giải · 13/13 testtrả lời trong 7.5 giây · thời gian chạy 141 ms · $0.02 ✓ min_window('ADOBECODEBANC', 'ABC')kỳ vọng 'BANC' 2 ms ✓ min_window('a', 'aa')kỳ vọng '' <1 ms ✓ min_window('a', 'a')kỳ vọng 'a' <1 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 73 ms⏱ 54 msCode
def min_window(s: str, t: str) -> str: if not t or len(t) > len(s): return "" need = {} for c in t: need[c] = need.get(c, 0) + 1 missing = len(t) l = 0 best_l, best_len = 0, len(s) + 1 get = need.get for r, c in enumerate(s): v = get(c, 0) if v > 0: missing -= 1 need[c] = v - 1 if missing == 0: while need[s[l]] < 0: need[s[l]] += 1 l += 1 w = r - l + 1 if w < best_len: best_len = w best_l = l need[s[l]] += 1 missing += 1 l += 1 if best_len > len(s): return "" return s[best_l:best_l + best_len]#2DeepSeek V4 Pro 0423đã giải · 13/13 testtrả lời trong 4.3 giây · thời gian chạy 326 ms · $0.0006 ✓ min_window('ADOBECODEBANC', 'ABC')kỳ vọng 'BANC' <1 ms ✓ min_window('a', 'aa')kỳ vọng '' <1 ms ✓ min_window('a', 'a')kỳ vọng 'a' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms⏱ 175 ms⏱ 143 msCode
from collections import Counter def min_window(s: str, t: str) -> str: if not t or not s: return "" need = Counter(t) missing = len(need) left = 0 start = 0 min_len = float('inf') for right, ch in enumerate(s): if ch in need: need[ch] -= 1 if need[ch] == 0: missing -= 1 while missing == 0: if right - left + 1 < min_len: min_len = right - left + 1 start = left left_char = s[left] if left_char in need: need[left_char] += 1 if need[left_char] > 0: missing += 1 left += 1 return s[start:start + min_len] if min_len != float('inf') else ""#2Google Gemini 3.8 Flashđã giải · 13/13 testtrả lời trong 6.7 giây · thời gian chạy 378 ms · $0.0017 ✓ min_window('ADOBECODEBANC', 'ABC')kỳ vọng 'BANC' 1 ms ✓ min_window('a', 'aa')kỳ vọng '' <1 ms ✓ min_window('a', 'a')kỳ vọng 'a' <1 ms ✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 196 ms⏱ 172 msCode
from collections import Counter def min_window(s: str, t: str) -> str: if not t or not s: return "" t_counts = Counter(t) required = len(t_counts) # Filter s to only keep characters present in t to speed up window sliding filtered_s = [(i, char) for i, char in enumerate(s) if char in t_counts] if not filtered_s: return "" l = 0 formed = 0 window_counts = {} # ans = (length, start_idx, end_idx) ans = (float('inf'), None, None) for r, (end_idx, char) in enumerate(filtered_s): window_counts[char] = window_counts.get(char, 0) + 1 if window_counts[char] == t_counts[char]: formed += 1 while l <= r and formed == required: start_idx, l_char = filtered_s[l] current_len = end_idx - start_idx + 1 if current_len < ans[0]: ans = (current_len, start_idx, end_idx) window_counts[l_char] -= 1 if window_counts[l_char] < t_counts[l_char]: formed -= 1 l += 1 return "" if ans[0] == float('inf') else s[ans[1]:ans[2] + 1]#4Mistral Devstral 2 2512đã giải · 13/13 testtrả lời trong 1.4 giây · thời gian chạy 584 ms · $0.0006 ✓ min_window('ADOBECODEBANC', 'ABC')kỳ vọng 'BANC' 3 ms ✓ min_window('a', 'aa')kỳ vọng '' <1 ms ✓ min_window('a', 'a')kỳ vọng 'a' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 225 ms⏱ 349 msCode
from collections import Counter def min_window(s: str, t: str) -> str: if not t or not s: return "" target_counts = Counter(t) required = len(target_counts) formed = 0 window_counts = Counter() left, right = 0, 0 min_len = float('inf') result = "" while right < len(s): char = s[right] window_counts[char] += 1 if char in target_counts and window_counts[char] == target_counts[char]: formed += 1 while left <= right and formed == required: char_left = s[left] current_len = right - left + 1 if current_len < min_len: min_len = current_len result = s[left:right+1] window_counts[char_left] -= 1 if char_left in target_counts and window_counts[char_left] < target_counts[char_left]: formed -= 1 left += 1 right += 1 return result
Chi phí token: $0.02 · Cách thức thi đấu và tính điểm →