Number of Substrings Containing All Three Characters ใน C++ : นับ Substring ที่มี a,b,c ครบ

ให้ String s ประกอบด้วย 'a', 'b', 'c' เท่านั้น หาจำนวน **Substrings** ที่มี **'a', 'b', 'c' อย่างน้อย 1 ตัวแต่ละตัว**

ตัวอย่าง

s = "abcabc"

Valid Substrings (10 ตัว): "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc", "abc" (Last)

Output: 10

แนวทาง: Sliding Window + Count Map (Two Pointers)

ใช้ j = Left Boundary ของ Window ที่ **Valid** (มี a,b,c ครบ) สำหรับ Right Pointer i

1. Expand i (Right) -> Add s[i] to Count Map
2. While Window [j..i] **Valid** (Count[a]>0 && Count[b]>0 && Count[c]>0):
   • Shrink Left: Count[s[j]]--, j++
3. ตอนนี้ j = **First Index ที่ทำให้ [j..i] Invalid** (หรือ j=0 ถ้ายัง Invalid)
4. **Number of Valid Substrings ending at i = j** (เพราะ Substring เริ่มที่ 0..j-1 จบที่ i จะ Valid ทั้งหมด)
5. ret += j

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

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

class Solution {
public:
    int numberOfSubstrings(string s) {
        int ret = 0;
        unordered_map<char, int> cnt;
        int j = 0; // Left pointer (first invalid start)

        for (int i = 0; i < s.size(); i++) {
            cnt[s[i]]++;

            // Shrink while valid
            while (cnt['a'] > 0 && cnt['b'] > 0 && cnt['c'] > 0) {
                cnt[s[j]]--;
                j++;
            }
            // j is now the first index where [j..i] is INVALID
            // So valid starts are 0, 1, ..., j-1 -> total j substrings ending at i
            ret += j;
        }
        return ret;
    }
};

Input / Output

Input:  "abcabc"
Output: 10

ความซับซ้อน (Complexity)

• Time: O(N) — แต่ละ Char Add/Remove จาก Map สูงสุด 1 ครั้ง
• Space: O(1) — Map มี Key แค่ 3 ตัว (a,b,c)

Intuition ของ ret += j

Window [j..i] เป็น **Shortest Valid Window ending at i** (หรือ Invalid ถ้า j=0 และยังไม่ครบ) -> Substrings ที่จบที่ i และ Valid คือที่เริ่มต้น 0, 1, ..., j-1 ทั้งหมด j ตัวครับ