นับเซิร์บสตริงไบนารีใน C++

ปัญหา

สมมติว่าเรามีสตริง s เราต้องหาจำนวนเซิร์บสตริงติดกันที่มีจำนวน 0 และ 1 เท่ากัน และ 0 ทั้งหมดและ 1 ทั้งหมดในเซิร์บสตริงเหล่านี้ถูกจัดกลุ่มติดกัน หากเซิร์บสตริงเกิดขึ้นหลายครั้ง ให้นับตามจำนวนครั้งที่เกิดขึ้น

เช่น ถ้าผนวกเข้าเป็น "11001100" ผลลัพธ์จะเป็น 6 เนื่องจากเซิร์บสตริงคือ "1100", "10", "0011", "01", "1100", "10"

วิธีแก้ปัญหา

1. กำหนดอาร์เรย์ cnt ขนาด 2 และเติมด้วย 0
2. res := 0
3. for i := 0 ถึง ความยาวของ s - 1 ทำ:
   • num := s[i] - ASCII ของ '0'
   • ถ้า i เท่ากับ 0 หรือ s[i] ไม่เท่ากับ s[i-1]: cnt[num] := 0
   • เพิ่ม cnt[num] ขึ้น 1
   • ถ้า cnt[num] <= cnt[1-num]: เพิ่ม res ขึ้น 1
4. คืนค่า res

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

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

class Solution { 
public: 
    int countBinarySubstrings(string s) { 
        int cnt[2] = { 0 }; 
        int res = 0; 
        for (int i = 0; i < s.length(); ++i) { 
            int num = s[i] - '0'; 
            if (i == 0 || s[i] != s[i - 1]) 
                cnt[num] = 0; 
            ++cnt[num]; 
            if (cnt[num] <= cnt[1 - num]) 
                ++res; 
        } 
        return res; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.countBinarySubstrings("11001100")); 
}

อินพุต

"11001100"

เอาต์พุต

6