นับ Substring ที่ตัวอักษรแต่ละตัวปรากฏไม่เกิน k ครั้งใน C++

เราได้รับสตริง str และตัวเลข k เป้าหมายคือนับ substring ที่ตัวอักษรแต่ละตัวปรากฏไม่เกิน k ครั้ง

ตัวอย่าง

อินพุต: str = "abaefgf", k = 1 (สมมติ)

เอาต์พุต: 9

คำอธิบาย: "a", "b", "a", "e", "f", "g", "f", "aba", "fgf"

อินพุต: str = "abcdef", k = 1

เอาต์พุต: 6

คำอธิบาย: "a", "b", "c", "d", "e", "f"

แนวทางการแก้ปัญหา (Naive O(n²))

สร้าง substring ทุกคู่ด้วย nested loop ใช้ array arr[26] นับความถี่ใน substring ปัจจุบัน ถ้าตัวไหนเกิน k ให้ break ลูปใน

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

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

int count_k(string str, int len, int k) {
    int count = 0;
    int arr[26];
    for (int i = 0; i < len; i++) {
        memset(arr, 0, sizeof(arr));
        for (int j = i; j < len; j++) {
            arr[str[j] - 'a']++;
            if (arr[str[j] - 'a'] <= k) {
                count++;
            } else {
                break;
            }
        }
    }
    return count;
}

int main() {
    string str = "bbddehj";
    int k = 1;
    int length = str.length();
    cout << "Count of substrings with each character occurring at most k times are: " << count_k(str, length, k);
    return 0;
}

เอาต์พุต

Count of substrings with each character occurring at most k times are: 14

หมายเหตุ: สามารถปรับปรุงเป็น O(n) ได้ด้วย sliding window 2 จุด