Chương trình đếm số ký tự khác biệt của mọi chuỗi con của một chuỗi trong Python

Cho chuỗi thường s, tính tổng số ký tự distinct (xuất hiện đúng 1 lần) trong mọi chuỗi con của s. Kết quả modulo 10^9+7.

Ví dụ: s = "xxy" → 6. Các chuỗi con: "x"(1), "x"(1), "y"(1), "xx"(0), "xy"(2), "xxy"(1).

Giải pháp

Đếm đóng góp của mỗi lần xuất hiện của ký tự:

• Với mỗi ký tự, lưu danh sách vị trí xuất hiện (thêm -1 ở đầu và n ở cuối)
• Với 3 vị trí liên tiếp left, middle, right: ký tự tại middle là distinct trong (middle-left)*(right-middle) chuỗi con
• Tổng cộng dồn ans = (ans + cnt) % MOD

Ví dụ minh họa

class Solution:
    def solve(self, s):
        m = 10 ** 9 + 7
        prev_seen = {}
        ans = 0
        def util(i, symbol):
            nonlocal ans
            prev = prev_seen.setdefault(symbol, [-1])
            prev.append(i)
            if len(prev) > 2:
                left = prev.pop(0)
                middle, right = prev
                cnt = (middle - left) * (right - middle)
                ans = (ans + cnt) % m
        for i, symbol in enumerate(s):
            util(i, symbol)
        for symbol in prev_seen:
            util(len(s), symbol)
        return ans

ob = Solution()
s = "xxy"
print(ob.solve(s))

Đầu vào

xxy

Đầu ra

6