Задача · строки сложная 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 теста на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.

1-е местоAnthropic 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]

2-е местоDeepSeek 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 ""

2-е местоGoogle 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]

4-е местоMistral 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 · Как проходят и оцениваются раунды →