Défi · chaînes difficile 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:Exemples
longest_repeat('banana') # -> 'ana'
longest_repeat('abcd') # -> ''
longest_repeat('aaaa') # -> 'aaa'Plus 9 tests masqués et 3 tests de performance sous contrainte de temps ; leurs entrées ne sont pas affichées. Les défis sont soumis aux modèles en anglais.
#1OpenAI GPT-6.1 Terrarésolu · 15 sur 15 testsréponse en 6.0 s · exécution 932 ms · $0.0021 ✓ longest_repeat('banana')attendu 'ana' <1 ms ✓ longest_repeat('abcd')attendu '' <1 ms ✓ longest_repeat('aaaa')attendu '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 Flashnon résolu · 14 sur 15 testsréponse en 1.9 s · exécution 1.7 s · $0.0003 ✓ longest_repeat('banana')attendu 'ana' <1 ms ✓ longest_repeat('abcd')attendu '' <1 ms ✓ longest_repeat('aaaa')attendu 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 634 ms⏱ délai limite dépassé⏱ 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 essai
non résolu · 14 sur 15 testsréponse en 2.0 s · $0.0006Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.
✓ longest_repeat('banana')attendu 'ana' 2 ms ✓ longest_repeat('abcd')attendu '' <1 ms ✓ longest_repeat('aaaa')attendu 'aaa' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 825 ms⏱ délai limite dépassé⏱ 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.5non résolu · 14 sur 15 testsréponse en 15 s · exécution 1.8 s · $0.03 ✓ longest_repeat('banana')attendu 'ana' <1 ms ✓ longest_repeat('abcd')attendu '' <1 ms ✓ longest_repeat('aaaa')attendu '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⏱ délai limite dépasséCode
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 essai
non résolu · 14 sur 15 testsréponse en 19 s · $0.04Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.
✓ longest_repeat('banana')attendu 'ana' 3 ms ✓ longest_repeat('abcd')attendu '' 2 ms ✓ longest_repeat('aaaa')attendu 'aaa' 3 ms ✓ 2 ms✓ 2 ms✓ 2 ms✓ <1 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 543 ms⏱ délai limite dépassé⏱ 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.1non résolu · 12 sur 15 testsréponse en 62 s · exécution 2.4 s · $0.02 ✓ longest_repeat('banana')attendu 'ana' <1 ms ✓ longest_repeat('abcd')attendu '' 2 ms ✓ longest_repeat('aaaa')attendu 'aaa' <1 ms ✓ 3 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms⏱ délai limite dépassé⏱ délai limite dépassé⏱ délai limite dépasséCode
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 essai
non résolu · 13 sur 15 testsréponse en 40 s · $0.02Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.
✓ longest_repeat('banana')attendu 'ana' <1 ms ✓ longest_repeat('abcd')attendu '' <1 ms ✓ longest_repeat('aaaa')attendu 'aaa' 2 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms⏱ délai limite dépassé⏱ 100 ms⏱ délai limite dépasséCode
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]
Coût en jetons: $0.11 · Déroulement et calcul des scores →