Đếm chuỗi con có mỗi ký tự xuất hiện tối đa k lần trong C++

Cho chuỗi str. Đếm chuỗi con mà mỗi ký tự trong chuỗi con xuất hiện tối đa k lần. Ví dụ "abc", k=1 → 6 chuỗi con ("a","b","c","ab","bc","abc").

Ví dụ

Đầu vào: str = "bbddehj", k = 1
Đầu ra: 14.

Giải thuật

Duyệt 2 vòng lặp tạo mọi chuỗi con str[i..j]. Dùng mảng arr[26] đếm tần suất ký tự trong chuỗi con hiện tại. Mở rộng j, nếu tần suất ký tự mới > k thì dừng mở rộng chuỗi con này.

Ví dụ triển khai

#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;
}

Kết quả

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