Task · strings hard Python ·
Longest repeated substring
Return the longest substring that occurs in s at least twice; the occurrences may overlap. If several substrings have that length, return the one whose first occurrence starts earliest. Return "" if no character repeats. s has lowercase letters only and can be up to 100,000 characters long.
Signature
def longest_repeat(s: str) -> str:Examples
longest_repeat('banana') # -> 'ana'
longest_repeat('abcd') # -> ''
longest_repeat('aaaa') # -> 'aaa'Plus 9 hidden tests and 3 large-input tests under a time limit; their inputs are not shown. Tasks are given to the models in English.
#1OpenAI GPT-6.1 Terrasolved · 15 of 15 testsanswer in 6.0 s · runtime 932 ms · $0.0021 ✓ longest_repeat('banana')expected 'ana' <1 ms ✓ longest_repeat('abcd')expected '' <1 ms ✓ longest_repeat('aaaa')expected 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 449 ms⏱ 165 ms⏱ 310 msCode
def longest_repeat(s: str) -> str: n = len(s) if n < 2: return "" transitions = [{}] links = [-1] lengths = [0] first_pos = [-1] last = 0 for i, ch in enumerate(s): cur = len(links) transitions.append({}) lengths.append(lengths[last] + 1) links.append(0) first_pos.append(i) p = last while p >= 0 and ch not in transitions[p]: transitions[p][ch] = cur p = links[p] if p >= 0: q = transitions[p][ch] if lengths[p] + 1 == lengths[q]: links[cur] = q else: clone = len(links) transitions.append(transitions[q].copy()) lengths.append(lengths[p] + 1) links.append(links[q]) first_pos.append(first_pos[q]) while p >= 0 and transitions[p].get(ch) == q: transitions[p][ch] = clone p = links[p] links[q] = clone links[cur] = clone last = cur best_len = 0 best_start = n for state in range(1, len(links)): parent = links[state] length = lengths[parent] if length >= best_len and length: start = first_pos[parent] - length + 1 if length > best_len or start < best_start: best_len = length best_start = start return s[best_start:best_start + best_len] if best_len else ""#2DeepSeek V4.1 Flashnot solved · 14 of 15 testsanswer in 1.9 s · runtime 1.7 s · $0.0003 ✓ 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✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 634 ms⏱ time limit exceeded⏱ 529 msCode
def longest_repeat(s: str) -> str: n = len(s) if n <= 1: return "" # build suffix array via prefix doubling sa = list(range(n)) rank = [ord(c) for c in s] k = 1 tmp = [0] * n while True: sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1)) tmp[sa[0]] = 0 for idx in range(1, n): a = sa[idx - 1] b = sa[idx] ra = rank[a] rb = rank[b] if ra != rb: tmp[b] = tmp[a] + 1 else: ra2 = rank[a + k] if a + k < n else -1 rb2 = rank[b + k] if b + k < n else -1 tmp[b] = tmp[a] + (1 if ra2 != rb2 else 0) rank, tmp = tmp, rank if rank[sa[-1]] == n - 1: break k <<= 1 # kasai LCP lcp = [0] * n p = [0] * n for i in range(n): p[sa[i]] = i h = 0 for i in range(n): r = p[i] if r > 0: j = sa[r - 1] while i + h < n and j + h < n and s[i + h] == s[j + h]: h += 1 lcp[r] = h if h: h -= 1 else: h = 0 best_len = 0 best_pos = 0 for r in range(1, n): l = lcp[r] if l > best_len: best_len = l best_pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r] elif l == best_len and l > 0: pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r] if pos < best_pos: best_pos = pos return s[best_pos:best_pos + best_len] if best_len > 0 else ""Second try
not solved · 14 of 15 testsanswer in 2.0 s · $0.0006The 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' 2 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⏱ 825 ms⏱ time limit exceeded⏱ 624 msCode
def longest_repeat(s: str) -> str: n = len(s) if n <= 1: return "" # Build suffix array using prefix doubling with counting sort (radix sort) sa = list(range(n)) rank = [ord(c) for c in s] k = 1 tmp = [0] * n while True: # Sort by (rank[i], rank[i+k]) using counting sort max_rank = max(rank) + 1 # Second key sort key2 = [rank[i + k] + 1 if i + k < n else 0 for i in range(n)] cnt = [0] * (max_rank + 1) for v in key2: cnt[v] += 1 for i in range(1, len(cnt)): cnt[i] += cnt[i - 1] sa2 = [0] * n for i in range(n - 1, -1, -1): v = key2[i] cnt[v] -= 1 sa2[cnt[v]] = i # First key sort key1 = [rank[i] for i in range(n)] cnt = [0] * max_rank for i in range(n): cnt[key1[sa2[i]]] += 1 for i in range(1, max_rank): cnt[i] += cnt[i - 1] for i in range(n - 1, -1, -1): v = key1[sa2[i]] cnt[v] -= 1 sa[cnt[v]] = sa2[i] # Reassign ranks tmp[sa[0]] = 0 for idx in range(1, n): a = sa[idx - 1] b = sa[idx] ra = rank[a] rb = rank[b] if ra != rb: tmp[b] = tmp[a] + 1 else: ra2 = rank[a + k] if a + k < n else -1 rb2 = rank[b + k] if b + k < n else -1 tmp[b] = tmp[a] + (1 if ra2 != rb2 else 0) rank, tmp = tmp, rank if rank[sa[-1]] == n - 1: break k <<= 1 # Kasai LCP lcp = [0] * n p = [0] * n for i in range(n): p[sa[i]] = i h = 0 for i in range(n): r = p[i] if r > 0: j = sa[r - 1] while i + h < n and j + h < n and s[i + h] == s[j + h]: h += 1 lcp[r] = h if h: h -= 1 else: h = 0 best_len = 0 best_pos = 0 for r in range(1, n): l = lcp[r] if l > best_len: best_len = l best_pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r] elif l == best_len and l > 0: pos = sa[r - 1] if sa[r - 1] < sa[r] else sa[r] if pos < best_pos: best_pos = pos return s[best_pos:best_pos + best_len] if best_len > 0 else ""#2Anthropic Claude Opus 5.5not solved · 14 of 15 testsanswer in 15 s · runtime 1.8 s · $0.03 ✓ 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⏱ 951 ms⏱ 117 ms⏱ time limit exceededCode
import random def longest_repeat(s: str) -> str: n = len(s) if n < 2: return "" M = (1 << 61) - 1 B = random.randrange(10**6, 10**9) H = [0] * (n + 1) P = [1] * (n + 1) h = 0 p = 1 for i, c in enumerate(s): h = (h * B + ord(c)) % M H[i + 1] = h p = p * B % M P[i + 1] = p def hashes(L): pl = P[L] return [(H[i + L] - H[i] * pl) % M for i in range(n - L + 1)] def ok(L): hs = hashes(L) return len(set(hs)) < len(hs) lo, hi = 0, n - 1 while lo < hi: mid = (lo + hi + 1) // 2 if ok(mid): lo = mid else: hi = mid - 1 L = lo if L == 0: return "" hs = hashes(L) seen = {} best = n for i, x in enumerate(hs): j = seen.get(x) if j is None: seen[x] = i elif j < best: best = j return s[best:best + L]Second try
not solved · 14 of 15 testsanswer in 19 s · $0.04The 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' 3 ms ✓ longest_repeat('abcd')expected '' 2 ms ✓ longest_repeat('aaaa')expected 'aaa' 3 ms ✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 543 ms⏱ time limit exceeded⏱ 445 msCode
import random def longest_repeat(s: str) -> str: n = len(s) if n < 2: return "" M = (1 << 61) - 1 B = random.randrange(10**6, 10**9) H = [0] * (n + 1) P = [1] * (n + 1) h = 0 p = 1 i = 1 for c in s.encode(): h = (h * B + c) % M H[i] = h p = p * B % M P[i] = p i += 1 def hashes(L): pl = P[L] return [(a - b * pl) % M for a, b in zip(H[L:], H)] def ok(L): if L <= 0: return True if L >= n: return False hs = hashes(L) return len(set(hs)) < len(hs) # galloping search lo = 0 step = 1 hi = None while True: cand = lo + step if cand >= n: hi = n - 1 break if ok(cand): lo = cand step *= 2 else: hi = cand - 1 break while lo < hi: mid = (lo + hi + 1) // 2 if ok(mid): lo = mid else: hi = mid - 1 L = lo if L == 0: return "" hs = hashes(L) seen = {} best = n for i, x in enumerate(hs): j = seen.get(x) if j is None: seen[x] = i elif j < best: best = j return s[best:best + L]#4SpaceXAI Grok Build 0.1not solved · 12 of 15 testsanswer in 62 s · runtime 2.4 s · $0.02 ✓ longest_repeat('banana')expected 'ana' <1 ms ✓ longest_repeat('abcd')expected '' 2 ms ✓ longest_repeat('aaaa')expected 'aaa' <1 ms ✓ 3 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 exceededCode
def longest_repeat(s: str) -> str: n = len(s) if n <= 1: return "" sa = list(range(n)) rank = [ord(c) for c in s] tmp = [0] * n k = 1 while k < n: sa.sort(key=lambda x: (rank[x], rank[x + k] if x + 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 prev_key < curr_key else 0) rank = tmp[:] k <<= 1 rnk = [0] * n for i in range(n): rnk[sa[i]] = i lcp = [0] * n h = 0 for i in range(n): if rnk[i] == n - 1: h = 0 continue j = sa[rnk[i] + 1] while i + h < n and j + h < n and s[i + h] == s[j + h]: h += 1 lcp[rnk[i]] = h if h > 0: h -= 1 max_l = max(lcp) if lcp else 0 if max_l == 0: return "" min_start = n for i in range(n - 1): if lcp[i] == max_l: start1 = sa[i] start2 = sa[i + 1] min_start = min(min_start, start1, start2) return s[min_start:min_start + max_l]Second try
not solved · 13 of 15 testsanswer in 40 s · $0.02The 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' 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ 100 ms⏱ time limit exceededCode
from collections import defaultdict def longest_repeat(s: str) -> str: n = len(s) if n <= 1: return "" MOD1 = 10**9 + 7 MOD2 = 10**9 + 9 BASE1 = 131 BASE2 = 137 pow1 = [1] * (n + 1) pow2 = [1] * (n + 1) pre1 = [0] * (n + 1) pre2 = [0] * (n + 1) for i in range(n): pow1[i + 1] = pow1[i] * BASE1 % MOD1 pow2[i + 1] = pow2[i] * BASE2 % MOD2 pre1[i + 1] = (pre1[i] * BASE1 + ord(s[i])) % MOD1 pre2[i + 1] = (pre2[i] * BASE2 + ord(s[i])) % MOD2 def get_h1(l, r): val = (pre1[r] - pre1[l] * pow1[r - l] % MOD1 + MOD1) % MOD1 return val def get_h2(l, r): val = (pre2[r] - pre2[l] * pow2[r - l] % MOD2 + MOD2) % MOD2 return val max_L = 0 low = 1 high = n - 1 while low <= high: mid = (low + high) // 2 seen = set() has = False for i in range(n - mid + 1): h1 = get_h1(i, i + mid) h2 = get_h2(i, i + mid) key = (h1, h2) if key in seen: has = True break seen.add(key) if has: max_L = mid low = mid + 1 else: high = mid - 1 if max_L == 0: return "" pos = defaultdict(list) for i in range(n - max_L + 1): h1 = get_h1(i, i + max_L) h2 = get_h2(i, i + max_L) key = (h1, h2) pos[key].append(i) min_start = n for lst in pos.values(): if len(lst) >= 2: min_start = min(min_start, lst[0]) return s[min_start:min_start + max_L]
Tokens cost: $0.11 · How rounds are run and scored →