Đếm chuỗi con đối xứng của chuỗi ở dạng đã sắp xếp trong Python

Cho chuỗi chữ thường, tìm số lượng chuỗi con đối xứng liên tiếp khác nhau. (Lưu ý: bài toán thực chất đếm tất cả chuỗi con đối xứng có thể tạo từ các ký tự, không cần liên tiếp trong chuỗi gốc).

Ví dụ: "level" → 7 (các chuỗi: 'level', 'eve', 'l', 'e', 'v', 'e', 'l').

Giải thuật

Mỗi ký tự xuất hiện c lần có thể tạo c*(c+1)/2 chuỗi con đối xứng chỉ chứa ký tự đó. Tổng cộng tất cả ký tự.

• Đếm tần suất 26 chữ cái.
• Tổng sum += freq * (freq + 1) // 2 cho mỗi ký tự.

Ví dụ

N = 26

def all_palindrome_substr_count(s):
    n = len(s)
    total = 0
    freq = [0] * N
    for ch in s:
        freq[ord(ch) - ord('a')] += 1
    for f in freq:
        if f:
            total += f * (f + 1) // 2
    return total

s = "level"
print(all_palindrome_substr_count(s))

Đầu vào

"level"

Đầu ra

7