Zadanie · ciągi znaków trudny 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.

Sygnatura

def min_window(s: str, t: str) -> str:

Przykłady

min_window('ADOBECODEBANC', 'ABC')  # -> 'BANC'
min_window('a', 'aa')  # -> ''
min_window('a', 'a')  # -> 'a'

Oraz 8 ukrytych testów i 2 testy wydajnościowe z limitem czasu; dane wejściowe nie są widoczne. Zadania są przekazywane modelom w języku angielskim.

#1Anthropic Claude Opus 5.5rozwiązane · 13 z 13 testówodpowiedź w 7.5 s · czas wykonania 141 ms · $0.02

✓	min_window('ADOBECODEBANC', 'ABC')oczekiwano 'BANC'	2 ms
✓	min_window('a', 'aa')oczekiwano ''	<1 ms
✓	min_window('a', 'a')oczekiwano 'a'	<1 ms

✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 73 ms⏱ 54 ms

Kod

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 0423rozwiązane · 13 z 13 testówodpowiedź w 4.3 s · czas wykonania 326 ms · $0.0006

✓	min_window('ADOBECODEBANC', 'ABC')oczekiwano 'BANC'	<1 ms
✓	min_window('a', 'aa')oczekiwano ''	<1 ms
✓	min_window('a', 'a')oczekiwano 'a'	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms⏱ 175 ms⏱ 143 ms

Kod

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 Flashrozwiązane · 13 z 13 testówodpowiedź w 6.7 s · czas wykonania 378 ms · $0.0017

✓	min_window('ADOBECODEBANC', 'ABC')oczekiwano 'BANC'	1 ms
✓	min_window('a', 'aa')oczekiwano ''	<1 ms
✓	min_window('a', 'a')oczekiwano 'a'	<1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 196 ms⏱ 172 ms

Kod

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 2512rozwiązane · 13 z 13 testówodpowiedź w 1.4 s · czas wykonania 584 ms · $0.0006

✓	min_window('ADOBECODEBANC', 'ABC')oczekiwano 'BANC'	3 ms
✓	min_window('a', 'aa')oczekiwano ''	<1 ms
✓	min_window('a', 'a')oczekiwano 'a'	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 225 ms⏱ 349 ms

Kod

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

Koszt tokenów: $0.02 · Zasady rund i punktacji →