Đếm số xâu con có đúng k ký tự khác nhau trong C++

Cho một xâu str[] chỉ chứa chữ cái thường và một giá trị nguyên k. Mục tiêu là tìm số lượng các xâu con có thể của str có đúng k phần tử khác biệt.

Ví dụ

Đầu vào

str="pqr" k=2

Đầu ra

Số xâu con có đúng k ký tự khác nhau là: 2

Giải thích

Các xâu con có đúng 2 phần tử khác biệt là: "pq", "qr".

Đầu vào

str="stristr" k=4

Đầu ra

Số xâu con có đúng k ký tự khác nhau là: 10

Giải thích

Các xâu con có đúng 4 phần tử khác biệt là: "stri", "tris", "rist", "istr", "stris", "trist", "ristr", "strist", "tristr", "stristr".

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ dùng một mảng array[26] để lưu tần suất các chữ cái tiếng Anh bên trong xâu str. Bây giờ duyệt str bằng hai vòng lặp for, nếu đối với xâu con, mỗi ký tự xuất hiện một lần thì tăng biến đếm ký tự duy nhất, ở cuối xâu con đó nếu biến đếm đó bằng k thì tăng biến đếm xâu con tuân theo điều kiện cho trước.

• Nhận xâu str làm đầu vào.
• Nhận số nguyên k với giá trị dương.
• Hàm substring_k(string str, int length, int k) nhận str và k và trả về số lượng xâu con có đúng k ký tự khác nhau.
• Khởi tạo biến đếm ban đầu là 0.
• Tạo mảng tần suất array[26].
• Duyệt str bằng hai vòng lặp for từ i=0 đến i<length và j=i đến j<length.
• Lấy temp là số phần tử duy nhất trong xâu con str[i đến j].
• Nếu array[str[j] - 'a'] == 0 thì ký tự str[j] xuất hiện lần đầu trong xâu con này. Vì vậy tăng temp.
• Bây giờ tăng số lượng ký tự hiện tại bằng array[str[j] - 'a']++.
• Nếu temp bằng k thì tăng biến đếm.
• Nếu temp lớn hơn k thì dừng tính toán thêm và thoát vòng lặp.
• Cuối cùng của tất cả vòng lặp trả về biến đếm làm kết quả.

Ví dụ mã

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

int substring_k(string str, int length, int k) {
    int count = 0;
    int array[26];
    
    for (int i = 0; i < length; i++) {
        int temp = 0;
        memset(array, 0, sizeof(array));
        
        for (int j = i; j < length; j++) {
            if (array[str[j] - 'a'] == 0) {
                temp++;
            }
            array[str[j] - 'a']++;
            
            if (temp == k) {
                count++;
            }
            
            if (temp > k) {
                break;
            }
        }
    }
    
    return count;
}

int main() {
    string str = "abc";
    int length = str.length();
    int k = 1;
    cout << "Số xâu con có đúng k ký tự khác nhau là: " << substring_k(str, length, k);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số xâu con có đúng k ký tự khác nhau là: 3