Đếm chuỗi con bắt đầu và kết thúc bằng '1' trong chuỗi nhị phân C++

Cho chuỗi nhị phân (chỉ chứa '0' và '1'). Đếm số chuỗi con (substring) bắt đầu bằng '1' và kết thúc bằng '1'. Ví dụ:

Đầu vào 1: "11101" (n=5) → Đầu ra: 6. Các chuỗi con: "11", "111", "1110", "11101", "1101", "101".

Đầu vào 2: "0011" → Đầu ra: 1 (chỉ "11").

Phương pháp: Toán học tổ hợp

Đếm số ký tự '1' trong chuỗi, gọi là cnt. Mỗi cặp '1' khác nhau tạo thành một chuỗi con bắt đầu và kết thúc bằng '1' (chọn 2 vị trí trong cnt vị trí). Số cặp = cnt * (cnt - 1) / 2.

Ví dụ mã nguồn

#include <iostream>
using namespace std;

int countSubstring(int N, string s) {
    int cnt = 0;
    for (char c : s) if (c == '1') cnt++;
    return cnt * (cnt - 1) / 2;
}

int main() {
    string str = "11101";
    cout << countSubstring(5, str); // 6
    return 0;
}

Kết quả

6

Chuỗi "11101" có 4 ký tự '1' → 4*3/2 = 6 chuỗi con.