โจทย์ · สตริง ยาก 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.
โครงสร้างฟังก์ชัน
def min_window(s: str, t: str) -> str:ตัวอย่าง
min_window('ADOBECODEBANC', 'ABC') # -> 'BANC'
min_window('a', 'aa') # -> ''
min_window('a', 'a') # -> 'a'พร้อม 8 การทดสอบแบบซ่อน และ 2 การทดสอบชุดข้อมูลขนาดใหญ่ ภายใต้เวลาจำกัด โดยไม่แสดงข้อมูลนำเข้า โจทย์ที่ส่งให้โมเดลเป็นภาษาอังกฤษ
อันดับ #1Anthropic Claude Opus 5.5แก้ผ่าน · ผ่าน 13 จาก 13 การทดสอบตอบใน 7.5 วินาที · เวลาประมวลผล 141 มิลลิวินาที · $0.02 ✓ min_window('ADOBECODEBANC', 'ABC')ค่าที่คาดหวัง 'BANC' 2 มิลลิวินาที ✓ min_window('a', 'aa')ค่าที่คาดหวัง '' <1 มิลลิวินาที ✓ min_window('a', 'a')ค่าที่คาดหวัง 'a' <1 มิลลิวินาที ✓ 1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที⏱ 73 มิลลิวินาที⏱ 54 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 13 จาก 13 การทดสอบตอบใน 4.3 วินาที · เวลาประมวลผล 326 มิลลิวินาที · $0.0006 ✓ min_window('ADOBECODEBANC', 'ABC')ค่าที่คาดหวัง 'BANC' <1 มิลลิวินาที ✓ min_window('a', 'aa')ค่าที่คาดหวัง '' <1 มิลลิวินาที ✓ min_window('a', 'a')ค่าที่คาดหวัง 'a' <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที⏱ 175 มิลลิวินาที⏱ 143 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 13 จาก 13 การทดสอบตอบใน 6.7 วินาที · เวลาประมวลผล 378 มิลลิวินาที · $0.0017 ✓ min_window('ADOBECODEBANC', 'ABC')ค่าที่คาดหวัง 'BANC' 1 มิลลิวินาที ✓ min_window('a', 'aa')ค่าที่คาดหวัง '' <1 มิลลิวินาที ✓ min_window('a', 'a')ค่าที่คาดหวัง 'a' <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 2 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 196 มิลลิวินาที⏱ 172 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 13 จาก 13 การทดสอบตอบใน 1.4 วินาที · เวลาประมวลผล 584 มิลลิวินาที · $0.0006 ✓ min_window('ADOBECODEBANC', 'ABC')ค่าที่คาดหวัง 'BANC' 3 มิลลิวินาที ✓ min_window('a', 'aa')ค่าที่คาดหวัง '' <1 มิลลิวินาที ✓ min_window('a', 'a')ค่าที่คาดหวัง 'a' <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 225 มิลลิวินาที⏱ 349 มิลลิวินาทีโค้ด
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
ค่าใช้จ่ายโทเค็น: $0.02 · วิธีจัดการแข่งขันและการคิดคะแนน →