Đếm số chuỗi con có chính xác k ký tự phân biệt trong C ++

Cho một chuỗi str [] chỉ chứa các bảng chữ cái viết thường và một giá trị nguyên k. Mục đích là để tìm số lượng các chuỗi con có thể có của str có đúng k phần tử khác nhau.

Ví dụ

Đầu vào

str= ”pqr” k=2

Đầu ra

Count of number of substrings with exactly k distinct characters are: 2

Giải thích

The substrings having exactly 2 distinct elements are: “pq”, “qr”.

Đầu vào

str= ”stristr” k=4

Đầu ra

Count of number of substrings with exactly k distinct characters are: 10

Giải thích

The substrings having exactly 2 distinct elements are:
“stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng ta sẽ tạo một mảng mảng [26] để lưu trữ tần số của các bảng chữ cái tiếng Anh bên trong chuỗi str. Bây giờ truy cập str bằng cách sử dụng hai vòng lặp for, nếu đối với chuỗi con, mỗi ký tự xuất hiện một lần sau đó tăng số lượng ký tự duy nhất, ở cuối chuỗi con đó nếu số lượng đó bằng k thì số lượng chuỗi con tăng dần theo các điều kiện đã cho.

• Lấy một chuỗi str làm đầu vào.

• Lấy một số nguyên k có giá trị dương.

• Hàm substring_k (chuỗi str, int length, int k) nhận str và k và trả về số lượng chuỗi con có chính xác k ký tự riêng biệt.

• Lấy số lượng ban đầu là 0.

• Lấy mảng mảng tần số [26].

• Traverse str bằng cách sử dụng hai vòng lặp for từ i =0 đến i

• Hãy tạm thời làm số lượng các phần tử duy nhất trong chuỗi con str [i đến j].

• Nếu mảng [str [j] - 'a'] ==0 thì ký tự str [j] này đã xuất hiện lần đầu tiên trong chuỗi con này. Vì vậy, nhiệt độ tăng dần.

• Bây giờ số gia tăng của ký tự hiện tại bằng cách sử dụng mảng [str [j] - 'a'] ++.

• Nếu nhiệt độ bằng k thì số gia tăng.

• Nếu nhiệt độ lớn hơn k thì hãy dừng việc đi lại xa hơn và ngắt vòng lặp.

• Kết quả là ở cuối tất cả các vòng lặp.

Ví dụ

#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<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of number of substrings with exactly k distinct characters are: 3