Đếm số substring của chuỗi nhị phân chứa đúng K ký tự '1' trong C++

Cho chuỗi nhị phân (chỉ chứa '0' và '1') và số nguyên k. Đếm số substring chứa đúng k ký tự '1'.

Ví dụ

Đầu vào − str = "10000100000", k = 2

Đầu ra − 6

Giải thích − Các substring có đúng 2 chữ '1': 6 trường hợp.

Đầu vào − str = "10000100000", k = 3

Đầu ra − 0

Giải thích − Chuỗi chỉ có 2 chữ '1', không thể có substring 3 chữ '1'.

Phương pháp giải

Dùng mảng tần suất tiền tố arr_fre lưu số lần xuất hiện của từng giá trị tổng tiền tố. Khởi tạo arr_fre[0] = 1. Duyệt chuỗi, cập nhật total_1 (số '1' đã thấy). Nếu total_1 >= k, cộng arr_fre[total_1 - k] vào kết quả. Sau đó tăng arr_fre[total_1]++.

• Hàm sub_k_ones(string str, int length, int k).
• Khởi tạo count = 0, total_1 = 0, mảng arr_fre[length+1] = {0}, arr_fre[0] = 1.
• Duyệt i = 0..length-1:
  • total_1 += str[i] - '0'.
  • Nếu total_1 >= k: count += arr_fre[total_1 - k].
  • arr_fre[total_1]++.
• Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int sub_k_ones(string str, int length, int k) {
    int count = 0;
    int total_1 = 0;
    int arr_fre[length + 1] = {0};
    arr_fre[0] = 1;
    for (int i = 0; i < length; i++) {
        total_1 += (str[i] - '0');
        if (total_1 >= k) count += arr_fre[total_1 - k];
        arr_fre[total_1]++;
    }
    return count;
}

int main() {
    string str = "10000100000";
    int length = str.length();
    int k = 2;
    cout << "Count of substrings of a binary string containing K ones are: " << sub_k_ones(str, length, k) << endl;
    return 0;
}

Đầu ra

Count of substrings of a binary string containing K ones are: 6