課題 · 文字列上級 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個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1OpenAI GPT-6.1 Terra正解 · 13 / 13 件のテストにパス回答時間 6.7 秒 · 実行時間 92 ms · $0.0015

✓	min_window('ADOBECODEBANC', 'ABC')期待値 'BANC'	<1 ms
✓	min_window('a', 'aa')期待値 ''	<1 ms
✓	min_window('a', 'a')期待値 'a'	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 29 ms⏱ 58 ms

コード

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)
    left = 0
    best_start = 0
    best_len = len(s) + 1

    for right, c in enumerate(s):
        if c in need:
            if need[c] > 0:
                missing -= 1
            need[c] -= 1

        while missing == 0:
            length = right - left + 1
            if length < best_len:
                best_start = left
                best_len = length
                if best_len == len(t):
                    return s[best_start:best_start + best_len]

            c = s[left]
            if c in need:
                need[c] += 1
                if need[c] > 0:
                    missing += 1
            left += 1

    return "" if best_len > len(s) else s[best_start:best_start + best_len]

#2MiniMax M3.1 Flash正解 · 13 / 13 件のテストにパス回答時間 7.3 秒 · 実行時間 156 ms · $0.0008

✓	min_window('ADOBECODEBANC', 'ABC')期待値 'BANC'	2 ms
✓	min_window('a', 'aa')期待値 ''	3 ms
✓	min_window('a', 'a')期待値 'a'	2 ms

✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 74 ms⏱ 68 ms

コード

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""

    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1

    missing = len(t)
    n = len(s)
    best_len = n + 1
    best_start = 0
    left = 0
    get = need.get

    for right in range(n):
        ch = s[right]
        cnt = get(ch)
        if cnt is not None:
            if cnt > 0:
                missing -= 1
            need[ch] = cnt - 1

        while missing == 0:
            cur = right - left + 1
            if cur < best_len:
                best_len = cur
                best_start = left
            c2 = s[left]
            n2 = get(c2)
            if n2 is not None:
                need[c2] = n2 + 1
                if n2 >= 0:
                    missing += 1
            left += 1

    if best_len > n:
        return ""
    return s[best_start:best_start + best_len]

#3DeepSeek V4 Pro 0423正解 · 13 / 13 件のテストにパス回答時間 4.4 秒 · 実行時間 241 ms · $0.0007

✓	min_window('ADOBECODEBANC', 'ABC')期待値 'BANC'	<1 ms
✓	min_window('a', 'aa')期待値 ''	<1 ms
✓	min_window('a', 'a')期待値 'a'	2 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 125 ms⏱ 103 ms

コード

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    from collections import Counter
    
    target = Counter(t)
    required = len(target)
    window_counts = {}
    formed = 0
    left = 0
    min_len = float('inf')
    min_left = 0
    
    for right, char in enumerate(s):
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in target and window_counts[char] == target[char]:
            formed += 1
        
        while left <= right and formed == required:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
            
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in target and window_counts[left_char] < target[left_char]:
                formed -= 1
            left += 1
    
    return s[min_left:min_left + min_len] if min_len != float('inf') else ""

#4Qwen3 Coder Next正解 · 13 / 13 件のテストにパス回答時間 5.5 秒 · 実行時間 437 ms · $0.0003

✓	min_window('ADOBECODEBANC', 'ABC')期待値 'BANC'	2 ms
✓	min_window('a', 'aa')期待値 ''	<1 ms
✓	min_window('a', 'a')期待値 'a'	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 135 ms⏱ 296 ms

コード

def min_window(s: str, t: str) -> str:
    if not t:
        return ""
    
    # Count characters in t
    from collections import Counter
    t_count = Counter(t)
    required = len(t_count)
    
    # Sliding window approach
    window_count = {}
    formed = 0
    left = 0
    right = 0
    min_len = float('inf')
    result = ""
    
    while right < len(s):
        # Add character from right to window
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1
        
        # Check if this character helps form a valid window
        if char in t_count and window_count[char] == t_count[char]:
            formed += 1
        
        # Try to contract the window from left while it's valid
        while left <= right and formed == required:
            # Update minimum window if current is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right+1]
            
            # Remove left character from window
            char = s[left]
            window_count[char] -= 1
            if char in t_count and window_count[char] < t_count[char]:
                formed -= 1
            left += 1
        
        right += 1
    
    return result

トークンコスト: $0.0032 · 対戦の進行と評価方法について →