Tóm tắt đề bài

Cho xâu ký tự \(S\) độ dài \(n \le 10^5\). Một xâu con liên tiếp được gọi là xâu đẹp nếu:

• Độ dài xâu con \(\ge 4\).
• Mọi đoạn con liên tiếp độ dài 4 của nó đều chứa ít nhất 3 loại ký tự khác nhau.

Yêu cầu: Đếm số lượng xâu con liên tiếp của \(S\) thỏa mãn điều kiện là xâu đẹp.

Phân tích

• Điều kiện "xấu": Một đoạn con độ dài 4 bị coi là "xấu" nếu nó chỉ chứa 1 hoặc 2 loại ký tự khác nhau.
• Định nghĩa lại xâu đẹp: Một xâu con \(S[L..R]\) (với \(R-L+1 \ge 4\)) là xâu đẹp nếu nó không chứa bất kỳ đoạn con độ dài 4 nào bị "xấu".
• Nhận xét quan trọng:
  • Nếu một xâu \(S[L..R]\) là xâu đẹp, thì mọi xâu con của nó có độ dài \(\ge 4\) cũng là xâu đẹp.
  • Với mỗi vị trí bắt đầu \(L\), nếu ta tìm được vị trí \(R\) xa nhất sao cho \(S[L..R]\) không chứa đoạn "xấu" nào, thì tất cả các xâu \(S[L..i]\) với \(L+3 \le i \le R\) đều là xâu đẹp.

Hướng giải quyết

Bước 1: Xác định các vị trí "xấu"

Duyệt qua toàn bộ xâu \(S\), với mỗi vị trí \(i\) từ \(0\) đến \(n-4\), kiểm tra xem đoạn \(S[i..i+3]\) có phải là đoạn "xấu" hay không (số lượng ký tự khác nhau \(\le 2\)).
Lưu chỉ số \(i\) của tất cả các đoạn "xấu" vào một danh sách bad.

Bước 2: Đếm số lượng xâu đẹp

Với mỗi vị trí bắt đầu \(L\) của xâu con (\(0 \le L \le n-4\)):

1. Tìm đoạn "xấu" đầu tiên xuất hiện tại vị trí \(i \ge L\). Gọi vị trí này là bad[p].
2. Nếu tồn tại một đoạn "xấu" như vậy, thì xâu con bắt đầu từ \(L\) chỉ có thể kéo dài tối đa đến vị trí \(R = bad[p] + 2\) để đảm bảo không chứa trọn vẹn đoạn "xấu" đó. Nói cách khác, điểm kết thúc \(i\) của xâu đẹp phải thỏa mãn \(L+3 \le i < bad[p] + 3\).
3. Nếu không còn đoạn "xấu" nào phía sau \(L\), xâu con có thể kéo dài đến tận cuối xâu \(S\) (\(i < n\)).
4. Số lượng xâu đẹp bắt đầu tại \(L\) sẽ là số lượng các giá trị \(i\) thỏa mãn điều kiện trên.

Kỹ thuật Hai con trỏ (Two Pointers)

Để tối ưu việc tìm đoạn "xấu" đầu tiên sau \(L\), ta sử dụng một biến con trỏ \(p\) chạy trên danh sách bad. Khi \(L\) tăng dần, \(p\) cũng chỉ tăng dần, giúp độ phức tạp duy trì ở mức tuyến tính.

Độ phức tạp

• Thời gian: \(O(n)\) do ta chỉ duyệt qua xâu một vài lần và danh sách bad có tối đa \(n\) phần tử. Việc kiểm tra 4 ký tự dùng set tốn \(O(1)\).
• Bộ nhớ: \(O(n)\) để lưu trữ xâu và danh sách các vị trí "xấu".

Code tham khảo

import sys

def solve():
    # Đọc dữ liệu và loại bỏ khoảng trắng thừa
    S = sys.stdin.read().strip()
    if not S:
        return
    n = len(S)

    # Bước 1: Tìm tất cả các vị trí i mà S[i:i+4] là đoạn "xấu"
    # Đoạn "xấu" là đoạn có <= 2 loại ký tự khác nhau
    bad = []
    for i in range(n - 3):
        # Sử dụng set để đếm số lượng ký tự khác nhau trong đoạn 4 ký tự
        if len(set(S[i:i+4])) <= 2:
            bad.append(i)

    ans = 0
    p = 0
    m = len(bad)

    # Bước 2: Với mỗi điểm đầu L, tìm điểm cuối R xa nhất có thể
    for L in range(n):
        # Di chuyển con trỏ p để tìm đoạn "xấu" đầu tiên bắt đầu từ L trở đi
        while p < m and bad[p] < L:
            p += 1

        # Nếu tìm thấy đoạn "xấu" tại bad[p], 
        # thì xâu con đẹp kết thúc tối đa tại (bad[p] + 3) - 1
        if p < m:
            R_limit = bad[p] + 3
        else:
            # Nếu không có đoạn xấu nào phía sau, có thể kéo dài đến cuối xâu
            R_limit = n

        # Các xâu đẹp bắt đầu tại L có thể kết thúc tại i thuộc [L+3, R_limit-1]
        # Số lượng xâu là: (R_limit - 1) - (L + 3) + 1 = R_limit - L - 3
        if R_limit - L >= 4:
            ans += (R_limit - L - 3)

    print(ans)

if __name__ == "__main__":
    solve()