Số lượng số 0 liên tiếp nhiều nhất trong chuỗi nhị phân nối tiếp trong C++

Cho chuỗi nhị phân độ dài n và số k. Nối chuỗi k lần, tìm số lượng ký tự '0' liên tiếp nhiều nhất trong chuỗi kết quả.

Ví dụ: str="0010010", k=2 -> nối thành "00100100010010" -> max 0 liên tiếp = 3.

Giải pháp:

• Nếu chuỗi toàn '0' -> kết quả = n * k.
• Ngược lại: tìm max độ dài substring toàn '0' trong chuỗi gốc (total_len).
• Tìm độ dài tiền tố toàn '0' (prefix) và hậu tố toàn '0' (suffix).
• Nếu k > 1, kết quả = max(total_len, prefix + suffix).

Ví dụ minh họa

#include <iostream>
using namespace std;

int max_length_substring(string str, int n, int k) {
    int total_len = 0, len = 0;
    for (int i = 0; i < n; ++i) {
        if (str[i] == '0') len++;
        else len = 0;
        total_len = max(total_len, len);
    }
    if (total_len == n) return n * k;
    int prefix = 0, suffix = 0;
    for (int i = 0; str[i] == '0'; ++i, ++prefix);
    for (int i = n - 1; str[i] == '0'; --i, ++suffix);
    if (k > 1) total_len = max(total_len, prefix + suffix);
    return total_len;
}

int main() {
    int k = 3;
    string str = "0010010";
    int res = max_length_substring(str, str.length(), k);
    cout << "Do dai max chuoi 0: " << res;
    return 0;
}

Kết quả

Do dai max chuoi 0: 3