Chương trình đếm số dãy con có i ký tự x, j ký tự y, k ký tự z trong Python

Mô tả bài toán

Cho chuỗi s chỉ chứa các ký tự 'x', 'y', 'z'. Tìm số lượng dãy con (subsequence) có dạng: i ký tự 'x' theo sau j ký tự 'y' theo sau k ký tự 'z', với i, j, k ≥ 1.

Ví dụ: s = "xxyz" → Kết quả: 3 (hai dãy "xyz" và một dãy "xxyz").

Thuật toán

1. Khởi tạo x = 0, y = 0, z = 0.
2. Duyệt từng ký tự của chuỗi:
   • Nếu ký tự 'x': x = x * 2 + 1
   • Nếu ký tự 'y': y = y * 2 + x
   • Nếu ký tự 'z': z = z * 2 + y
3. Trả về z.

Giải thích logic

• x: số dãy con chỉ chứa 'x' (ít nhất 1). Mỗi 'x' mới có thể: không lấy, hoặc lấy thêm vào các dãy cũ → nhân 2, cộng 1 (dãy chỉ chứa 'x' mới này).
• y: số dãy con dạng x...xy...y. Mỗi 'y' mới: không lấy (nhân 2), hoặc nối vào sau các dãy x...x (cộng x).
• z: số dãy con dạng x...xy...yz...z. Mỗi 'z' mới: không lấy (nhân 2), hoặc nối vào sau các dãy x...xy...y (cộng y).

Triển khai Python

class Solution:
    def solve(self, s: str) -> int:
        n = len(s)
        x = 0
        y = 0
        z = 0
        for i in range(n):
            if s[i] == "x":
                x *= 2
                x += 1
            if s[i] == "y":
                y *= 2
                y += x
            if s[i] == "z":
                z *= 2
                z += y
        return z

ob = Solution()
print(ob.solve("xxyz"))

Đầu vào: "xxyz"

Đầu ra: 3