Subtask chung: $t \leq 500$
Giới hạn:
Có tối đa 500 chuỗi đầu vào.
Hướng tiếp cận

• Đối với mỗi chuỗi, xử lý từng ký tự theo chiều dài chuỗi để tính số đoạn và kiểm tra mẫu "WB".
• Độ dài tối đa của mỗi chuỗi ảnh hưởng đến cách tối ưu hóa.

Subtask 1 (05%): chuỗi toàn "W" hoặc "B"
Ta có thể hiểu rắng:

• Nếu chuỗi toàn "W" hoặc "B", chỉ có 1 đoạn duy nhất, và không có mẫu "WB".
• Kết quả luôn là $cnt = 1$ (không cần giảm $ok$).

Cách xử lý:

• Kiểm tra nếu toàn bộ ký tự trong chuỗi giống nhau ($s[i] = s[0]$ với mọi $i$).
• Nếu đúng, trực tiếp trả về $1$.

Độ phức tạp:

Subtask 2 (15%): $1 \leq |S| \leq 10$
Giới hạn:

• Chuỗi rất ngắn (dài tối đa 10).
• Có thể xử lý trực tiếp từng ký tự với độ phức tạp $\mathcal{O}(|S|)$.

Hướng giải:

• Với mỗi chuỗi:
• Duyệt qua tất cả các cặp ký tự liên tiếp để đếm số đoạn ($cnt$).
• Kiểm tra mẫu "WB" xuất hiện hay không.
• Tính kết quả: $cnt - ok$.

Độ phức tạp:

• Với $t \leq 500$, tổng độ phức tạp là $\mathcal{O}(t \cdot |S|) = \mathcal{O}(500 \cdot 10) = \mathcal{O}(5000)$.

Subtask 3 (30%): $1 \leq |S| \leq 100$
Giới hạn:

• Độ dài chuỗi lên đến 100.
• Số lượng chuỗi $t \leq 500$.

Hướng giải:

• Giống subtask 2 nhưng cần tối ưu hơn:

1.Chỉ duyệt qua mỗi ký tự $s[i]$ một lần để:

• Đếm số đoạn khi $s[i] \neq s[i-1]$. \item Kiểm tra mẫu "WB" khi $s[i] = 'W'$ và $s[i+1] = 'B'$.
• Tính kết quả sau khi duyệt hết chuỗi.

Độ phức tạp:

• Với mỗi chuỗi dài tối đa 100 ký tự, tổng độ phức tạp là $\mathcal{O}(t \cdot |S|) = \mathcal{O}(500 \cdot 100) = \mathcal{O}(50,000)$.

Subtask 4(50%): $1 \leq |S| \leq 1000$

Giới hạn

• Độ dài chuỗi lên đến 1000.
• Số lượng chuỗi $t \leq 500$.

Hướng giải

• Tương tự subtask 3, nhưng cần đặc biệt lưu ý tối ưu hóa:
• Duyệt một lần qua chuỗi:
• Đếm số đoạn bằng cách so sánh $s[i]$ và $s[i-1]$.
• Kiểm tra mẫu "WB" khi $s[i] = 'W'$ và $s[i+1] = 'B'$.
• Không lưu trữ trạng thái thừa thãi, xử lý trực tiếp trên dữ liệu đầu vào.

Độ phức tạp: