結果

問題 No.765 ukuku 2
ユーザー qwewe
提出日時 2025-05-14 13:10:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,553 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 91,688 KB
最終ジャッジ日時 2025-05-14 13:12:06
合計ジャッジ時間 6,705 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 9 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

# Function to compute the length of the Longest Common Subsequence (LCS)
# between two strings S and SR using an O(N log N) approach, where N = len(S).
# This is used to find the length of the Longest Palindromic Subsequence (LPS)
# by computing LCS(S, S_reversed).
def compute_LCS_NlogN(S, SR):
    """
    Computes the length of the Longest Common Subsequence (LCS) between strings S and SR.
    Uses an approach based on finding the Longest Increasing Subsequence (LIS) 
    on indices of matching characters, optimized to O(N log N).

    Args:
        S: The first string.
        SR: The second string (typically the reverse of S for LPS computation).

    Returns:
        The length of the LCS of S and SR.
    """
    N = len(S)
    if N == 0:
        return 0

    # Precompute positions of each character in the second string SR.
    # Store positions as lists indexed by character code (0-25 for 'a'-'z').
    # This avoids dictionary overhead and might be slightly faster.
    pos_in_SR_list = [[] for _ in range(26)]
    for j in range(N):
        char_code = ord(SR[j]) - ord('a')
        pos_in_SR_list[char_code].append(j)

    # `tails` list stores the smallest ending index `j` in SR 
    # for a common subsequence of length `k+1`.
    # Specifically, `tails[k]` holds the smallest ending index `j` in SR 
    # for an LCS of length `k+1`. This is analogous to the Patience Sorting algorithm for LIS.
    tails = [] 

    # Iterate through the first string S character by character.
    for i in range(N):
        char_code = ord(S[i]) - ord('a')
        
        # Retrieve the list of indices where this character appears in SR.
        # The list could be empty if the character S[i] is not present in SR.
        indices_j = pos_in_SR_list[char_code]
        
        # If the character S[i] exists in SR:
        if indices_j:
            # Process these positions `j` in decreasing order.
            # This order is crucial for correctness when characters repeat.
            # It ensures that for a fixed `i`, multiple matches `j` are handled
            # such that earlier occurrences `j` in SR can potentially start
            # longer common subsequences.
            for j in reversed(indices_j):
                # Find the insertion point for `j` in the `tails` list using binary search.
                # `bisect_left(tails, j)` returns the smallest index `idx` such that `tails[idx] >= j`.
                idx = bisect.bisect_left(tails, j)
                
                # If `idx == len(tails)`, it means `j` is greater than all current tail elements
                # stored in `tails`. This signifies that the match (i, j) extends the 
                # longest common subsequence found so far by one.
                if idx == len(tails):
                    tails.append(j)
                # Otherwise, `j` is less than or equal to `tails[idx]`.
                # This means we've found a common subsequence of length `idx+1` that ends at index `j` in SR.
                # If `j` is smaller than the current `tails[idx]`, it provides a "better" ending point
                # for an LCS of length `idx+1` (smaller ending index `j` might allow for more extensions later).
                # We update `tails[idx]` with `j`.
                else:
                    tails[idx] = j

    # The length of the LCS is simply the number of elements currently stored in `tails`.
    return len(tails)

# Main part of the solution
def solve():
    # Read input string S from standard input.
    S = sys.stdin.readline().strip()
    N = len(S)

    # Handle edge cases for empty or single-character strings.
    # If N <= 1, deleting one character results in an empty or single-character string.
    # The longest palindrome in an empty string has length 0.
    # The longest palindrome in a single-char string has length 1.
    # However, the problem statement says N >= 2. Let's check N=2.
    # If N=2, S=s1s2. Delete s1 -> s2 (LPS 1). Delete s2 -> s1 (LPS 1). Max is 1.
    # Let's adjust the base case logic to N<=1 returning 0.
    if N <= 1:
       # According to constraints N >= 2. But robust code handles this.
       # If N=1, delete the only char -> empty string, LPS=0.
       # If N=0, empty string, LPS=0.
       print(0)
       return

    # Compute the reverse of S.
    SR = S[::-1]

    # Compute the length of the Longest Palindromic Subsequence (LPS) of S.
    # This is equivalent to finding the LCS between S and its reverse SR.
    L = compute_LCS_NlogN(S, SR)

    # The core logic derived from analysis:
    # If the length L of the LPS of S equals N, it implies S itself is a palindrome.
    # In this case, deleting any single character from S will result in a string S'.
    # The maximum possible LPS length for any such S' is N-1. This maximum is achievable.
    if L == N:
        print(N - 1)
    # If L < N, S is not a palindrome whose length equals N.
    # It can be shown that there exists at least one character in S whose removal
    # does not affect *some* specific Longest Palindromic Subsequence P of length L.
    # Therefore, after deleting such a character, the resulting string S' still contains P as a subsequence.
    # The LPS length of S' is at least L. Since deleting a character cannot increase the LPS length,
    # the maximum LPS length achievable after deleting one character is exactly L.
    else:
        print(L)

# Execute the solver function wrapped in a check for script execution context.
if __name__ == '__main__':
    solve()
0