Aufgabe · Strings schwer 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'

• Platz 1OpenAI GPT-6.1 Terragelöst · 13 von 13 TestsAntwort in 6.7 s · Laufzeit 92 ms · $0.0015

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

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

  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]

• Platz 2MiniMax M3.1 Flashgelöst · 13 von 13 TestsAntwort in 7.3 s · Laufzeit 156 ms · $0.0008

  ✓	min_window('ADOBECODEBANC', 'ABC')erwartet 'BANC'	2 ms
  ✓	min_window('a', 'aa')erwartet ''	3 ms
  ✓	min_window('a', 'a')erwartet 'a'	2 ms

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

  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]

• Platz 3DeepSeek V4 Pro 0423gelöst · 13 von 13 TestsAntwort in 4.4 s · Laufzeit 241 ms · $0.0007

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

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

  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 ""

• Platz 4Qwen3 Coder Nextgelöst · 13 von 13 TestsAntwort in 5.5 s · Laufzeit 437 ms · $0.0003

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

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

  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

Token-Kosten: $0.0032 · So laufen Runden und Wertung ab →