Aufgabe · Strings schwer Python ·

Longest repeated substring

def longest_repeat(s: str) -> str:

longest_repeat('banana')  # -> 'ana'
longest_repeat('abcd')  # -> ''
longest_repeat('aaaa')  # -> 'aaa'

• Platz 1SpaceXAI Grok Build 0.1nicht gelöst · 13 von 15 TestsAntwort in 78 s · Laufzeit 2.0 s · $0.02

  ✓	longest_repeat('banana')erwartet 'ana'	1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ Zeitlimit überschritten⏱ 101 ms⏱ Zeitlimit überschritten
  Code

  def longest_repeat(s: str) -> str:
      if not s:
          return ""
      n = len(s)
      MOD1 = 10**9 + 7
      MOD2 = 10**9 + 9
      BASE1 = 131
      BASE2 = 137
      h1 = [0] * (n + 1)
      h2 = [0] * (n + 1)
      p1 = [1] * (n + 1)
      p2 = [1] * (n + 1)
      for i in range(n):
          h1[i + 1] = (h1[i] * BASE1 + ord(s[i])) % MOD1
          h2[i + 1] = (h2[i] * BASE2 + ord(s[i])) % MOD2
          p1[i + 1] = p1[i] * BASE1 % MOD1
          p2[i + 1] = p2[i] * BASE2 % MOD2
      def get_h(l, r):
          length = r - l
          val1 = (h1[r] - h1[l] * p1[length] % MOD1 + MOD1) % MOD1
          val2 = (h2[r] - h2[l] * p2[length] % MOD2 + MOD2) % MOD2
          return (val1, val2)
      def has_repeat(L):
          if L == 0:
              return True
          if L > n:
              return False
          seen = set()
          for i in range(n - L + 1):
              h = get_h(i, i + L)
              if h in seen:
                  return True
              seen.add(h)
          return False
      low = 0
      high = n
      while low < high:
          mid = (low + high + 1) // 2
          if has_repeat(mid):
              low = mid
          else:
              high = mid - 1
      maxL = low
      if maxL == 0:
          return ""
      pos = {}
      for i in range(n - maxL + 1):
          h = get_h(i, i + maxL)
          if h not in pos:
              pos[h] = []
          pos[h].append(i)
      min_first = n + 1
      best = ""
      for h, lst in pos.items():
          if len(lst) >= 2:
              first = lst[0]
              if first < min_first:
                  min_first = first
                  best = s[first: first + maxL]
      return best

  Zweiter Versuch

  nicht gelöst · 12 von 15 TestsAntwort in 50 s · $0.02

  Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.

  ✓	longest_repeat('banana')erwartet 'ana'	<1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ Zeitlimit überschritten⏱ Zeitlimit überschritten⏱ Zeitlimit überschritten

  Code

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
      sa = list(range(n))
      sa.sort(key=lambda i: s[i])
      rank = [0] * n
      rank[sa[0]] = 0
      for i in range(1, n):
          if s[sa[i]] != s[sa[i-1]]:
              rank[sa[i]] = rank[sa[i-1]] + 1
          else:
              rank[sa[i]] = rank[sa[i-1]]
      k = 1
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
          new_rank = [0] * n
          new_rank[sa[0]] = 0
          for i in range(1, n):
              p = sa[i-1]
              c = sa[i]
              if (rank[p], rank[p + k] if p + k < n else -1) != (rank[c], rank[c + k] if c + k < n else -1):
                  new_rank[c] = new_rank[p] + 1
              else:
                  new_rank[c] = new_rank[p]
          rank = new_rank
          k <<= 1
      rank_pos = [0] * n
      for i in range(n):
          rank_pos[sa[i]] = i
      lcp = [0] * n
      h = 0
      for i in range(n):
          if rank_pos[i] == 0:
              h = 0
              continue
          j = sa[rank_pos[i] - 1]
          if h > 0:
              h -= 1
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[rank_pos[i]] = h
      max_l = 0
      for val in lcp:
          if val > max_l:
              max_l = val
      if max_l == 0:
          return ""
      min_start = n
      for i in range(1, n):
          if lcp[i] >= max_l:
              min_start = min(min_start, sa[i-1], sa[i])
      return s[min_start:min_start + max_l]

• Platz 2OpenAI GPT-5.3-Codexnicht gelöst · 12 von 15 TestsAntwort in 7.9 s · Laufzeit 1.8 s · $0.0095

  ✓	longest_repeat('banana')erwartet 'ana'	<1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ Falsche Antwort⏱ Zeitlimit überschritten⏱ Falsche Antwort
  Code

  from typing import List
  
  def longest_repeat(s: str) -> str:
      n = len(s)
      if n <= 1:
          return ""
  
      # Suffix array (prefix-doubling, O(n log n))
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
  
          r = 0
          tmp[sa[0]] = 0
          for i in range(1, n):
              a, b = sa[i - 1], sa[i]
              pa = (rank[a], rank[a + k] if a + k < n else -1)
              pb = (rank[b], rank[b + k] if b + k < n else -1)
              if pa != pb:
                  r += 1
              tmp[b] = r
  
          rank, tmp = tmp, rank
          if r == n - 1:
              break
          k <<= 1
  
      # Kasai LCP array, O(n)
      inv = [0] * n
      for i, p in enumerate(sa):
          inv[p] = i
  
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          pos = inv[i]
          if pos == n - 1:
              h = 0
              continue
          j = sa[pos + 1]
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[pos] = h
          if h:
              h -= 1
  
      best_len = 0
      best_start = 0
  
      i = 0
      m = n - 1
      while i < m:
          if lcp[i] == 0:
              i += 1
              continue
          if lcp[i] < best_len:
              i += 1
              continue
  
          cur_max = lcp[i]
          min_pos = min(sa[i], sa[i + 1])
  
          j = i
          while j + 1 < m and lcp[j + 1] > 0:
              j += 1
              if lcp[j] > cur_max:
                  cur_max = lcp[j]
              p = sa[j + 1]
              if p < min_pos:
                  min_pos = p
  
          if cur_max > best_len:
              best_len = cur_max
              best_start = min_pos
          elif cur_max == best_len and cur_max > 0 and min_pos < best_start:
              best_start = min_pos
  
          i = j + 1
  
      if best_len == 0:
          return ""
      return s[best_start:best_start + best_len]

  Zweiter Versuch

  nicht gelöst · 14 von 15 TestsAntwort in 11 s · $0.01

  Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.

  ✓	longest_repeat('banana')erwartet 'ana'	1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 803 ms⏱ Zeitlimit überschritten⏱ 591 ms

  Code

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
  
      # Build suffix array with O(n log n) counting-sort doubling
      sa = list(range(n))
      rank = [ord(c) - 96 for c in s]  # 1..26
      tmp = [0] * n
      k = 1
      maxv = max(27, n) + 5
  
      while True:
          m = max(max(rank) + 2, n + 2, 30)
  
          # sort by second key rank[i+k]
          cnt = [0] * m
          sec = [0] * n
          for i in range(n):
              v = rank[i + k] if i + k < n else 0
              sec[i] = v
              cnt[v] += 1
          ssum = 0
          for i in range(m):
              c = cnt[i]
              cnt[i] = ssum
              ssum += c
          sa2 = [0] * n
          for idx in sa:
              v = sec[idx]
              sa2[cnt[v]] = idx
              cnt[v] += 1
  
          # sort by first key rank[i]
          cnt = [0] * m
          for i in range(n):
              cnt[rank[i]] += 1
          ssum = 0
          for i in range(m):
              c = cnt[i]
              cnt[i] = ssum
              ssum += c
          sa_new = [0] * n
          for idx in sa2:
              v = rank[idx]
              sa_new[cnt[v]] = idx
              cnt[v] += 1
          sa = sa_new
  
          # re-rank
          r = 1
          tmp[sa[0]] = r
          for i in range(1, n):
              a = sa[i - 1]
              b = sa[i]
              a1 = rank[a]
              b1 = rank[b]
              a2 = rank[a + k] if a + k < n else 0
              b2 = rank[b + k] if b + k < n else 0
              if a1 != b1 or a2 != b2:
                  r += 1
              tmp[b] = r
          rank, tmp = tmp, rank
          if r == n:
              break
          k <<= 1
  
      # Kasai LCP
      pos = [0] * n
      for i, p in enumerate(sa):
          pos[p] = i
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          pi = pos[i]
          if pi == n - 1:
              h = 0
              continue
          j = sa[pi + 1]
          while i + h < n and j + h < n and s[i + h] == s[j + h]:
              h += 1
          lcp[pi] = h
          if h:
              h -= 1
  
      best_len = 0
      best_start = 0
      for i, v in enumerate(lcp):
          if v > best_len:
              best_len = v
              a = sa[i]
              b = sa[i + 1]
              best_start = a if a < b else b
          elif v == best_len and v > 0:
              a = sa[i]
              b = sa[i + 1]
              st = a if a < b else b
              if st < best_start:
                  best_start = st
  
      return s[best_start:best_start + best_len] if best_len > 0 else ""

• Platz 3DeepSeek V4 Pro 0423nicht gelöst · 12 von 15 TestsAntwort in 7.0 s · Laufzeit 2.4 s · $0.0011

  ✓	longest_repeat('banana')erwartet 'ana'	<1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 5 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ Zeitlimit überschritten⏱ Zeitlimit überschritten⏱ Zeitlimit überschritten
  Code

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      
      # Suffix array construction using doubling algorithm
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      
      while k < n:
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
          tmp[sa[0]] = 0
          for i in range(1, n):
              prev = sa[i-1]
              curr = sa[i]
              prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
              curr_key = (rank[curr], rank[curr + k] if curr + k < n else -1)
              tmp[curr] = tmp[prev] + (1 if curr_key != prev_key else 0)
          rank, tmp = tmp, rank
          k <<= 1
      
      # LCP array construction using Kasai's algorithm
      inv_sa = [0] * n
      for i, idx in enumerate(sa):
          inv_sa[idx] = i
      
      lcp = [0] * (n - 1)
      h = 0
      for i in range(n):
          if inv_sa[i] > 0:
              j = sa[inv_sa[i] - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              lcp[inv_sa[i] - 1] = h
              if h > 0:
                  h -= 1
      
      # Find maximum LCP and earliest suffix position
      max_len = 0
      min_pos = n
      for i in range(n - 1):
          if lcp[i] > max_len:
              max_len = lcp[i]
              min_pos = min(sa[i], sa[i + 1])
          elif lcp[i] == max_len and max_len > 0:
              min_pos = min(min_pos, sa[i], sa[i + 1])
      
      if max_len == 0:
          return ""
      return s[min_pos:min_pos + max_len]

  Zweiter Versuch

  nicht gelöst · 14 von 15 TestsAntwort in 7.1 s · $0.0016

  Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.

  ✓	longest_repeat('banana')erwartet 'ana'	<1 ms
  ✓	longest_repeat('abcd')erwartet ''	<1 ms
  ✓	longest_repeat('aaaa')erwartet 'aaa'	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms⏱ 656 ms⏱ Zeitlimit überschritten⏱ 498 ms

  Code

  def longest_repeat(s: str) -> str:
      n = len(s)
      if n < 2:
          return ""
      
      # Suffix array construction using SA-IS algorithm for O(n) time
      # but here we implement a fast doubling with integer keys
      sa = list(range(n))
      rank = [ord(c) - 97 for c in s]
      tmp = [0] * n
      k = 1
      
      while k < n:
          # Use tuple sorting with a key lambda is still O(n log n), but more efficient in Python
          sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
          tmp[sa[0]] = 0
          for i in range(1, n):
              prev = sa[i-1]
              curr = sa[i]
              prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
              curr_key = (rank[curr], rank[curr + k] if curr + k < n else -1)
              tmp[curr] = tmp[prev] + (1 if curr_key != prev_key else 0)
          rank, tmp = tmp, rank
          if rank[sa[-1]] == n - 1:
              break
          k <<= 1
      
      # LCP array using Kasai's algorithm
      inv_sa = [0] * n
      for i, idx in enumerate(sa):
          inv_sa[idx] = i
      
      max_len = 0
      min_pos = n
      h = 0
      for i in range(n):
          if inv_sa[i] > 0:
              j = sa[inv_sa[i] - 1]
              while i + h < n and j + h < n and s[i + h] == s[j + h]:
                  h += 1
              if h > max_len:
                  max_len = h
                  min_pos = min(i, j)
              elif h == max_len and h > 0:
                  min_pos = min(min_pos, i, j)
              if h > 0:
                  h -= 1
      
      if max_len == 0:
          return ""
      return s[min_pos:min_pos + max_len]

• Platz 4MoonshotAI Kimi K2.7 Codenicht gelöst · 0 von 15 TestsAntwort in 120 s

  Kein Code in der Antwort

  ✗	longest_repeat('banana')erwartet 'ana'Kein Code in der Antwort	—
  ✗	longest_repeat('abcd')erwartet ''Kein Code in der Antwort	—
  ✗	longest_repeat('aaaa')erwartet 'aaa'Kein Code in der Antwort	—

  ✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort✗ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort⏱ Kein Code in der Antwort

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