Завдання · рядки складний Python ·

Longest palindromic substring

Return the longest substring of s that reads the same backwards. If several have that length, return the leftmost. s has lowercase letters only and can be up to 200,000 characters long.

Сигнатура

def longest_palindrome(s: str) -> str:

Приклади

longest_palindrome('babad')  # -> 'bab'
longest_palindrome('cbbd')  # -> 'bb'
longest_palindrome('')  # -> ''

Плюс 9 прихованих тестів і 3 тести на великих даних з лімітом часу; їхній ввід не відображається. Завдання надсилаються моделям англійською мовою.

#1Anthropic Claude Sonnet 5.5розв'язано · 15 з 15 тестіввідповідь за 6.0 с · виконання 806 мс · $0.0090

✓	longest_palindrome('babad')очікувалося 'bab'	<1 мс
✓	longest_palindrome('cbbd')очікувалося 'bb'	<1 мс
✓	longest_palindrome('')очікувалося ''	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 306 мс⏱ 265 мс⏱ 226 мс

Код

def longest_palindrome(s: str) -> str:
    if not s:
        return ''
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    c = r = 0
    best = 0
    bi = 0
    for i in range(1, n - 1):
        if i < r:
            k = p[2 * c - i]
            m = r - i
            pi = k if k < m else m
        else:
            pi = 0
        while t[i + pi + 1] == t[i - pi - 1]:
            pi += 1
        p[i] = pi
        if i + pi > r:
            c = i
            r = i + pi
        if pi > best:
            best = pi
            bi = i
    start = (bi - best) // 2
    return s[start:start + best]

#2OpenAI GPT-6.1 Terraрозв'язано · 15 з 15 тестіввідповідь за 6.1 с · виконання 1.1 с · $0.0023

✓	longest_palindrome('babad')очікувалося 'bab'	<1 мс
✓	longest_palindrome('cbbd')очікувалося 'bb'	1 мс
✓	longest_palindrome('')очікувалося ''	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 2 мс✓ 1 мс✓ <1 мс✓ 1 мс✓ <1 мс⏱ 427 мс⏱ 322 мс⏱ 329 мс

Код

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    best_start = 0
    best_len = 1

    odd = [0] * n
    left, right = 0, -1
    for i in range(n):
        k = 1 if i > right else min(odd[left + right - i], right - i + 1)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        odd[i] = k
        length = 2 * k - 1
        start = i - k + 1
        if length > best_len or (length == best_len and start < best_start):
            best_len, best_start = length, start
        if i + k - 1 > right:
            left, right = i - k + 1, i + k - 1

    even = [0] * n
    left, right = 0, -1
    for i in range(n):
        k = 0 if i > right else min(even[left + right - i + 1], right - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        even[i] = k
        length = 2 * k
        start = i - k
        if length > best_len or (length == best_len and start < best_start):
            best_len, best_start = length, start
        if i + k - 1 > right:
            left, right = i - k, i + k - 1

    return s[best_start:best_start + best_len]

#2Google Gemini 3.8 Flashрозв'язано · 15 з 15 тестіввідповідь за 11 с · виконання 1.2 с · $0.0032

✓	longest_palindrome('babad')очікувалося 'bab'	<1 мс
✓	longest_palindrome('cbbd')очікувалося 'bb'	<1 мс
✓	longest_palindrome('')очікувалося ''	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 428 мс⏱ 389 мс⏱ 331 мс

Код

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    t = "^#" + "#".join(s) + "#$"
    n = len(t)
    p = [0] * n
    c = 0
    r = 0

    max_len = 0
    best_start = 0

    for i in range(1, n - 1):
        i_mirror = 2 * c - i
        if r > i:
            p[i] = min(r - i, p[i_mirror])
        else:
            p[i] = 0

        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
            p[i] += 1

        if i + p[i] > r:
            c = i
            r = i + p[i]

        length = p[i]
        if length > max_len:
            max_len = length
            best_start = (i - length) // 2

    return s[best_start : best_start + max_len]

#2Qwen3.8 Max (0902)розв'язано · 15 з 15 тестіввідповідь за 23 с · виконання 1.4 с · $0.0074

✓	longest_palindrome('babad')очікувалося 'bab'	<1 мс
✓	longest_palindrome('cbbd')очікувалося 'bb'	<1 мс
✓	longest_palindrome('')очікувалося ''	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 441 мс⏱ 444 мс⏱ 467 мс

Код

def longest_palindrome(s: str) -> str:
    if not s:
        return ''
    
    # Manacher's algorithm
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    P = [0] * n
    
    center = 0
    right = 0
    
    best_center = 0
    best_len = 0
    
    for i in range(n):
        mirror = 2 * center - i
        
        if i < right:
            P[i] = min(right - i, P[mirror])
        
        while i - P[i] - 1 >= 0 and i + P[i] + 1 < n and t[i - P[i] - 1] == t[i + P[i] + 1]:
            P[i] += 1
        
        if i + P[i] > right:
            center = i
            right = i + P[i]
        
        if P[i] > best_len:
            best_len = P[i]
            best_center = i
    
    start = (best_center - best_len) // 2
    return s[start:start + best_len]

Вартість токенів: $0.02 · Як проходять раунди та нараховується рейтинг →