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'

• #1Anthropic Claude Opus 5.5selesai · 13 dari 13 pengujianrespons dalam 7.5 dtk · waktu eksekusi 141 md · $0.02

  ✓	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✓ 2 md✓ 2 md✓ 2 md⏱ 73 md⏱ 54 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)
      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 0423selesai · 13 dari 13 pengujianrespons dalam 4.3 dtk · waktu eksekusi 326 md · $0.0006

  ✓	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⏱ 175 md⏱ 143 md
  Kode

  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 Flashselesai · 13 dari 13 pengujianrespons dalam 6.7 dtk · waktu eksekusi 378 md · $0.0017

  ✓	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✓ 2 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md✓ <1 md⏱ 196 md⏱ 172 md
  Kode

  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 2512selesai · 13 dari 13 pengujianrespons dalam 1.4 dtk · waktu eksekusi 584 md · $0.0006

  ✓	min_window('ADOBECODEBANC', 'ABC')diharapkan 'BANC'	3 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⏱ 225 md⏱ 349 md
  Kode

  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

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