代码出现Time Limit Exceeded问题，求优化Lapindrome判断逻辑

Hey there! Let's tackle that Time Limit Exceeded error you're hitting with your Lapindrome checking code. First, let's recap what a Lapindrome is to make sure we're on the same page:

A Lapindrome is a string that splits into two halves (ignoring the middle character if length is odd) where both halves have the exact same characters with identical frequencies. Examples like "gaga", "abccab", and "rotor" qualify, while "abbaab" does not.

Most timeout issues here come from inefficient character comparison methods or slow input handling. Here are the key optimizations to get your code running fast:

1. Use Array-Based Frequency Counting (Instead of Sorting or Dictionaries) #

Sorting substrings to compare them is a common approach, but it adds an O(n log n) overhead that can kill performance for large strings. Instead, use a fixed-size array (since we're dealing with lowercase letters, a 26-element array works perfectly) to count character frequencies for each half. This brings the time complexity down to O(n), which is way faster.

Here's a sample implementation:

def is_lapindrome(s):
    n = len(s)
    mid = n // 2
    freq_left = [0] * 26
    freq_right = [0] * 26
    
    # Count frequencies for the first half
    for i in range(mid):
        freq_left[ord(s[i]) - ord('a')] += 1
    
    # Count frequencies for the second half (skip middle char if odd length)
    start_idx = mid if n % 2 == 0 else mid + 1
    for i in range(start_idx, n):
        freq_right[ord(s[i]) - ord('a')] += 1
    
    # Compare the frequency arrays directly
    return freq_left == freq_right

2. Speed Up Input Handling #

If you're processing multiple test cases, using input() in a loop can be surprisingly slow because of repeated I/O calls. Instead, read all input at once using sys.stdin.read() and split it into a list. This reduces the overhead of multiple I/O operations, which is often the bottleneck for timeout errors.

Example of efficient input handling:

import sys

def main():
    # Read all input in one go
    all_input = sys.stdin.read().split()
    test_cases = int(all_input[0])
    
    for i in range(1, test_cases + 1):
        current_string = all_input[i]
        print("YES" if is_lapindrome(current_string) else "NO")

if __name__ == "__main__":
    main()

3. Skip Unnecessary String Copies #

Avoid creating substrings (like s[:mid] or s[mid+1:]) because slicing creates a new copy of the characters, which wastes memory and time. Instead, iterate over the original string's indices directly, like we did in the frequency counting example above.

These changes should drastically reduce your code's runtime and eliminate the Time Limit Exceeded error. The array-based frequency check is both time and space efficient, and bulk input handling cuts down on I/O delays that often sneak up on you.

内容的提问来源于stack exchange，提问作者Utkarsh Pandey