Opdracht · strings moeilijk Python ·

Longest repeated substring

def longest_repeat(s: str) -> str:

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

• #1SpaceXAI Grok Build 0.1niet opgelost · 13 van 15 testsantwoord in 78 s · looptijd 2.0 s · $0.02

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

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ 101 ms⏱ tijdslimiet overschreden
  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

  Tweede poging

  niet opgelost · 12 van 15 testsantwoord in 50 s · $0.02

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ tijdslimiet overschreden⏱ tijdslimiet overschreden

  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]

• #2OpenAI GPT-5.3-Codexniet opgelost · 12 van 15 testsantwoord in 7.9 s · looptijd 1.8 s · $0.0095

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ verkeerd antwoord⏱ tijdslimiet overschreden⏱ verkeerd antwoord
  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]

  Tweede poging

  niet opgelost · 14 van 15 testsantwoord in 11 s · $0.01

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 803 ms⏱ tijdslimiet overschreden⏱ 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 ""

• #3DeepSeek V4 Pro 0423niet opgelost · 12 van 15 testsantwoord in 7.0 s · looptijd 2.4 s · $0.0011

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

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 5 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ tijdslimiet overschreden⏱ tijdslimiet overschreden
  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]

  Tweede poging

  niet opgelost · 14 van 15 testsantwoord in 7.1 s · $0.0016

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms⏱ 656 ms⏱ tijdslimiet overschreden⏱ 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]

• #4MoonshotAI Kimi K2.7 Codeniet opgelost · 0 van 15 testsantwoord in 120 s

  geen code in het antwoord

  ✗	longest_repeat('banana')verwacht 'ana'geen code in het antwoord	—
  ✗	longest_repeat('abcd')verwacht ''geen code in het antwoord	—
  ✗	longest_repeat('aaaa')verwacht 'aaa'geen code in het antwoord	—

  ✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord✗ geen code in het antwoord⏱ geen code in het antwoord⏱ geen code in het antwoord⏱ geen code in het antwoord

Tokenkosten: $0.06 · Hoe rondes verlopen en worden beoordeeld →