結果

問題 No.765 ukuku 2
ユーザー lam6er
提出日時 2025-04-16 00:24:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,040 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 81,404 KB
実行使用メモリ 76,180 KB
最終ジャッジ日時 2025-04-16 00:25:47
合計ジャッジ時間 7,817 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 16 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #

def can_delete_one(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        else:
            # Check deleting left character
            l, r = left + 1, right
            valid = True
            while l < r:
                if s[l] != s[r]:
                    valid = False
                    break
                l += 1
                r -= 1
            if valid:
                return True
            # Check deleting right character
            l, r = left, right - 1
            valid = True
            while l < r:
                if s[l] != s[r]:
                    valid = False
                    break
                l += 1
                r -= 1
            return valid
    return True

def max_palindrome(s):
    n = len(s)
    max_len = 0
    for i in range(n):
        # Odd length palindromes
        l, r = i, i
        while l >= 0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        # After expansion, try deleting left or right and expand again
        # Delete left (original l is now out of valid range)
        new_l, new_r = l + 1, r - 1
        len1 = new_r - new_l + 1
        # Delete right
        new_l, new_r = l + 1, r - 1
        len2 = new_r - new_l + 1
        current_max = max(len1, len2)
        # Expand after deletion
        # Delete left and expand
        ll, lr = l, r - 1
        while ll >= 0 and lr < n and s[ll] == s[lr]:
            ll -= 1
            lr += 1
        len_after_del_left = lr - ll - 1
        # Delete right and expand
        rl, rr = l + 1, r
        while rl >= 0 and rr < n and s[rl] == s[rr]:
            rl -= 1
            rr += 1
        len_after_del_right = rr - rl - 1
        current_max = max(current_max, len_after_del_left, len_after_del_right)
        max_len = max(max_len, current_max)
        # Even length palindromes
        l, r = i, i + 1
        if r >= n:
            continue
        while l >= 0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        # After expansion, try deleting left or right and expand again
        # Delete left
        new_l, new_r = l + 1, r - 1
        len1 = new_r - new_l + 1
        # Delete right
        new_l, new_r = l + 1, r - 1
        len2 = new_r - new_l + 1
        current_max = max(len1, len2)
        # Expand after deletion
        # Delete left and expand
        ll, lr = l, r - 1
        while ll >= 0 and lr < n and s[ll] == s[lr]:
            ll -= 1
            lr += 1
        len_after_del_left = lr - ll - 1
        # Delete right and expand
        rl, rr = l + 1, r
        while rl >= 0 and rr < n and s[rl] == s[rr]:
            rl -= 1
            rr += 1
        len_after_del_right = rr - rl - 1
        current_max = max(current_max, len_after_del_left, len_after_del_right)
        max_len = max(max_len, current_max)
    return max_len

s = input().strip()
n = len(s)
if can_delete_one(s):
    print(n - 1)
else:
    print(max_palindrome(s))
0