นับ Substring ที่มีจำนวน 0, 1, 2 เท่ากันใน C++

เราได้รับสตริง str ที่มีแต่ '0', '1', '2' เป้าหมายคือหา substring ที่มีจำนวน 0, 1, 2 เท่ากันทุกตัว

ตัวอย่าง

อินพุต: str = "112200120"

เอาต์พุต: 5

คำอธิบาย: "112200", "122001", "012", "120", "201"

อินพุต: str = "12012"

เอาต์พุต: 3

คำอธิบาย: "120", "201", "012"

แนวทางการแก้ปัญหา (Prefix Difference + Hash Map)

กำหนด count0, count1, count2 เป็น prefix count
สร้าง key = (count0 - count1, count0 - count2)
ใช้ map นับ frequency ของแต่ละ key
เริ่มต้น key (0,0) มี frequency 1
เมื่อเจอ key เดียวกัน แสดงว่าระหว่าง 2 จุดมี count0, count1, count2 เพิ่มขึ้นเท่ากัน → valid substring

การนำไปใช้ (Implementation)

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

int countSubstrings(string str) {
    int len = str.length();
    map<pair<int,int>, int> mp;
    mp[{0,0}] = 1;
    
    int count0 = 0, count1 = 0, count2 = 0;
    int result = 0;
    
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') count0++;
        else if (str[i] == '1') count1++;
        else count2++;
        
        pair<int,int> key = {count0 - count1, count0 - count2};
        result += mp[key];
        mp[key]++;
    }
    return result;
}

int main() {
    string str = "112200120";
    cout << "Count of Substrings with equal number of 0s, 1s and 2s are: " << countSubstrings(str);
    return 0;
}

เอาต์พุต

Count of Substrings with equal number of 0s, 1s and 2s are: 5

หมายเหตุ: โค้ดต้นฉบับในตัวอย่างมีบั๊ก (ใช้ฟังก์ชันผิด) โค้ดข้างบนเป็นการนำไปใช้ที่ถูกต้อง