टास्क · स्ट्रिंग्स कठिन 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.
सिग्नेचर
def longest_repeat(s: str) -> str:उदाहरण
longest_repeat('banana') # -> 'ana'
longest_repeat('abcd') # -> ''
longest_repeat('aaaa') # -> 'aaa'साथ ही 9 हिडन टेस्ट्स और समय सीमा के तहत 3 लार्ज-इनपुट टेस्ट्स; इनके इनपुट दिखाए नहीं गए हैं। टास्क मॉडल्स को अंग्रेज़ी में दिए जाते हैं।
#1OpenAI GPT-6.1 Terraहल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 6.0 s · रनटाइम 932 ms · $0.0021 ✓ longest_repeat('banana')अपेक्षित 'ana' <1 ms ✓ longest_repeat('abcd')अपेक्षित '' <1 ms ✓ longest_repeat('aaaa')अपेक्षित '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 msकोड
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 Flashहल नहीं हुआ · 15 में से 14 टेस्ट्स पासजवाब का समय 1.9 s · रनटाइम 1.7 s · $0.0003 ✓ longest_repeat('banana')अपेक्षित 'ana' <1 ms ✓ longest_repeat('abcd')अपेक्षित '' <1 ms ✓ longest_repeat('aaaa')अपेक्षित '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 msकोड
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 ""दूसरा प्रयास
हल नहीं हुआ · 15 में से 14 टेस्ट्स पासजवाब का समय 2.0 s · $0.0006मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।
✓ longest_repeat('banana')अपेक्षित 'ana' 2 ms ✓ longest_repeat('abcd')अपेक्षित '' <1 ms ✓ longest_repeat('aaaa')अपेक्षित '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 msकोड
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.5हल नहीं हुआ · 15 में से 14 टेस्ट्स पासजवाब का समय 15 s · रनटाइम 1.8 s · $0.03 ✓ longest_repeat('banana')अपेक्षित 'ana' <1 ms ✓ longest_repeat('abcd')अपेक्षित '' <1 ms ✓ longest_repeat('aaaa')अपेक्षित '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 exceeded)कोड
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]दूसरा प्रयास
हल नहीं हुआ · 15 में से 14 टेस्ट्स पासजवाब का समय 19 s · $0.04मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।
✓ longest_repeat('banana')अपेक्षित 'ana' 3 ms ✓ longest_repeat('abcd')अपेक्षित '' 2 ms ✓ longest_repeat('aaaa')अपेक्षित '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 msकोड
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.1हल नहीं हुआ · 15 में से 12 टेस्ट्स पासजवाब का समय 62 s · रनटाइम 2.4 s · $0.02 ✓ longest_repeat('banana')अपेक्षित 'ana' <1 ms ✓ longest_repeat('abcd')अपेक्षित '' 2 ms ✓ longest_repeat('aaaa')अपेक्षित '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 exceeded)कोड
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]दूसरा प्रयास
हल नहीं हुआ · 15 में से 13 टेस्ट्स पासजवाब का समय 40 s · $0.02मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।
✓ longest_repeat('banana')अपेक्षित 'ana' <1 ms ✓ longest_repeat('abcd')अपेक्षित '' <1 ms ✓ longest_repeat('aaaa')अपेक्षित '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 exceeded)कोड
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]
टोकन लागत: $0.11 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →