結果

問題 No.1617 Palindrome Removal
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:11:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 4,704 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 65,672 KB
最終ジャッジ日時 2025-05-14 13:13:17
合計ジャッジ時間 2,417 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to check if a string is a palindrome
# It compares the string with its reverse.
def check_palindrome(s):
    return s == s[::-1]

# Function to check if all characters in a string are the same
# It checks if the length of the set of characters is 1.
# Handles edge case N=0, though problem constraints say N >= 1.
def check_all_same(s, n):
    if n <= 1:
        return True
    # A more direct check without using set:
    first_char = s[0]
    # Since we know S is a palindrome (this check is only called when S is a palindrome),
    # we only need to check characters in the first half. If they are all same as S[0],
    # then the symmetric characters in the second half are also S[0].
    # The loop runs up to N // 2 index. Index N // 2 is the middle character for odd N.
    for i in range(1, n // 2 + 1): 
        if s[i] != first_char:
            return False
    return True


def solve():
    # Read input string S from stdin
    S = sys.stdin.readline().strip()
    N = len(S)

    # Check if S is a palindrome
    is_palindrome = check_palindrome(S)

    if not is_palindrome:
        # If S is not a palindrome, we can choose to remove 0 characters (k=0 is even).
        # The resulting string is S itself, which is not a palindrome.
        # The maximum possible length is N, since we removed the minimum possible even number of characters (0).
        print(N)
        return

    # S is a palindrome
    
    # Check if all characters in S are the same
    all_same = check_all_same(S, N)
    
    if all_same:
        # S consists of only one distinct character, S = c^N. Example: 'aaaa', 'z'.
        # We must remove k characters, where k is a positive even integer (k>=2), 
        # or k=0 if S is already non-palindrome (not this case).
        # Removing k characters results in S' = c^(N-k).
        # If N-k >= 1, S' is a palindrome (e.g., 'aa', 'a').
        # If N-k = 0, S' is the empty string "".
        # Based on sample outputs ('aaaa' -> 0), it seems the empty string is considered non-palindrome for this problem.
        # We can obtain the empty string iff we remove k=N characters.
        # This is allowed only if N is an even number.
        # If N is even (and N >= 2), we can remove N characters to get "". Length 0. This is the only non-palindrome possible. Max length is 0.
        # If N is odd, we cannot remove N characters (since N is odd, k=N is not allowed). Any allowed even k < N results in N-k >= 1 (since N is odd, N-k is odd, so N-k >= 1).
        # All possible resulting strings S' = c^(N-k) are palindromes of length >= 1.
        # Thus, if N is odd, we cannot form a non-palindrome. Output -1.
        
        if N % 2 == 1:
            # Odd length string with all same chars, like 'z', 'aaa'. Can't form non-palindrome.
            print("-1")
        else:
            # Even length string with all same chars, like 'aa', 'aaaa'. Can form "" (length 0) by removing N chars.
            print(0)
             
    else:
        # S is a palindrome and contains at least two distinct characters.
        # Examples: 'aba', 'racecar', 'aaabbbaaa'.
        # N must be at least 3 for a palindrome to have distinct characters (e.g. 'aba').
        # We must remove k characters, k >= 2 and k is even.
        # To maximize length N-k, we should minimize k. The minimum is k=2.
        # The resulting length is N-2.
        
        # Consider N=3 case, e.g., 'aba'. Removing 2 characters results in a string of length 1.
        # Any string of length 1 is a palindrome. Cannot form a non-palindrome by removing 2 chars.
        # Cannot remove more characters (k=4 not possible for N=3). So output -1.
        
        # Consider N >= 4 case. Example: 'racecar', 'aaabbbaaa'.
        # Claim: It is always possible to remove 2 characters to obtain a non-palindrome.
        # Intuition: Since there are distinct characters, the symmetry can be broken by removing 2 carefully chosen characters.
        # Example: S = 'aaabbbaaa', N=9. Remove S[0], S[1] ('a', 'a'). Result 'abbbaaa'. Not palindrome. Length 7 = N-2.
        # Example: S = 'racecar', N=7. Remove S[0], S[1] ('r', 'a'). Result 'cecar'. Not palindrome. Length 5 = N-2.
        # So the maximum length is N-2.
        
        # Check N value:
        # N=1, N=2: Palindromes must have all same chars, handled by the `all_same` branch.
        # If we reach here, N must be >= 3.
        if N == 3: 
             # Case like 'aba'. Result length 1 is always palindrome.
             print("-1")
        else: # N >= 4
             # Max length is N-2 by removing 2 characters appropriately.
             print(N - 2)

# Execute the solve function
solve()
0