Task · strings hard 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.1not solved · 13 of 15 testsanswer in 78 s · runtime 2.0 s · $0.02

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

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ time limit exceeded⏱ 101 ms⏱ time limit exceeded
  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

  Second try

  not solved · 12 of 15 testsanswer in 50 s · $0.02

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ time limit exceeded⏱ time limit exceeded

  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-Codexnot solved · 12 of 15 testsanswer in 7.9 s · runtime 1.8 s · $0.0095

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ wrong answer⏱ time limit exceeded⏱ wrong answer
  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]

  Second try

  not solved · 14 of 15 testsanswer in 11 s · $0.01

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 803 ms⏱ time limit exceeded⏱ 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 0423not solved · 12 of 15 testsanswer in 7.0 s · runtime 2.4 s · $0.0011

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

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 5 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ time limit exceeded⏱ time limit exceeded
  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]

  Second try

  not solved · 14 of 15 testsanswer in 7.1 s · $0.0016

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms⏱ 656 ms⏱ time limit exceeded⏱ 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 Codenot solved · 0 of 15 testsanswer in 120 s

  no code in the answer

  ✗	longest_repeat('banana')expected 'ana'no code in the answer	—
  ✗	longest_repeat('abcd')expected ''no code in the answer	—
  ✗	longest_repeat('aaaa')expected 'aaa'no code in the answer	—

  ✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer✗ no code in the answer⏱ no code in the answer⏱ no code in the answer⏱ no code in the answer

Tokens cost: $0.06 · How rounds are run and scored →