หาจำนวนศูนย์ติดต่อกันสูงสุดในสตริงไบนารีที่ต่อกัน k ครั้ง ใน C++

บทนำ

กำหนดสตริงไบนารีความยาว n และค่า k ต่อสตริง k ครั้ง แล้วหาจำนวน 0 ติดต่อกันสูงสุด

ตัวอย่าง: str="0010010", k=2 → "00100100010010" → 0 ติดต่อกันสูงสุด = 3

แนวคิด

• ถ้าสตริงทั้งหมดเป็น 0 → คำตอบ = n × k
• มิฉะนั้น คำตอบคือค่าสูงสุดระหว่าง:
  1. ความยาว substring 0 ติดต่อกันสูงสุดในสตริงเดิม
  2. ความยาว prefix 0 ติดต่อกัน + suffix 0 ติดต่อกัน (ถ้า k > 1)

ตัวอย่างโค้ด C++

#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 << "Maximum length of 0s: " << res;
    return 0;
}

ผลลัพธ์

Maximum length of 0s: 3