Tugas · string sulit Python ·

Minimum window substring

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

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

• #1OpenAI GPT-6.1 Terraselesai · 13 dari 13 pengujianrespons dalam 6.7 dtk · waktu eksekusi 92 md · $0.0015

  ✓	min_window('ADOBECODEBANC', 'ABC')diharapkan 'BANC'	<1 md
  ✓	min_window('a', 'aa')diharapkan ''	<1 md
  ✓	min_window('a', 'a')diharapkan 'a'	<1 md

  ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 29 md⏱ 58 md
  Kode

  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 Flashselesai · 13 dari 13 pengujianrespons dalam 7.3 dtk · waktu eksekusi 156 md · $0.0008

  ✓	min_window('ADOBECODEBANC', 'ABC')diharapkan 'BANC'	2 md
  ✓	min_window('a', 'aa')diharapkan ''	3 md
  ✓	min_window('a', 'a')diharapkan 'a'	2 md

  ✓ 2 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 74 md⏱ 68 md
  Kode

  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 0423selesai · 13 dari 13 pengujianrespons dalam 4.4 dtk · waktu eksekusi 241 md · $0.0007

  ✓	min_window('ADOBECODEBANC', 'ABC')diharapkan 'BANC'	<1 md
  ✓	min_window('a', 'aa')diharapkan ''	<1 md
  ✓	min_window('a', 'a')diharapkan 'a'	2 md

  ✓ <1 md✓ <1 md✓ <1 md✓ 2 md✓ 2 md✓ 2 md✓ 2 md✓ 1 md⏱ 125 md⏱ 103 md
  Kode

  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 Nextselesai · 13 dari 13 pengujianrespons dalam 5.5 dtk · waktu eksekusi 437 md · $0.0003

  ✓	min_window('ADOBECODEBANC', 'ABC')diharapkan 'BANC'	2 md
  ✓	min_window('a', 'aa')diharapkan ''	<1 md
  ✓	min_window('a', 'a')diharapkan 'a'	<1 md

  ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 135 md⏱ 296 md
  Kode

  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

Biaya token: $0.0032 · Cara babak dijalankan dan dinilai →