Đếm chuỗi con với mỗi ký tự xuất hiện nhiều nhất k lần trong C ++

Chúng tôi được cung cấp một chuỗi str. Mục đích là để đếm số chuỗi con trong str có mỗi ký tự xuất hiện tối đa k lần. Ví dụ:nếu đầu vào là “abc” và k =1, các chuỗi con sẽ là “a”, “b”, “c”, “ab”, “bc”, “abc”.

Hãy cho chúng tôi hiểu với các ví dụ.

Đầu vào - str =”abaefgf”

Đầu ra - Số chuỗi con có cùng ký tự đầu tiên và ký tự cuối cùng là &mmius; 9

Giải thích - Các chuỗi con sẽ là

“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.

Đầu vào - str =”abcdef”

Đầu ra - Số chuỗi con có ký tự đầu tiên và ký tự cuối cùng là:6

Giải thích - Các chuỗi con sẽ -

“a” , “b” , “c”, “d”, “e” ,”f”. Total 6

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

Có thể có nhiều cách tiếp cận để giải quyết vấn đề đã cho, tức là cách tiếp cận ngây thơ và cách tiếp cận hiệu quả. Vì vậy, trước tiên chúng ta hãy xem xét cách tiếp cận ngây thơ. Chúng ta sẽ chuyển các chuỗi con có độ dài mọi chiều vào một hàm check (). Nếu chuỗi con đó bắt đầu và kết thúc bằng cùng một ký tự thì hãy tăng số lượng.

• Lấy chuỗi str. Tính độ dài dưới dạng str.size ().

• Kiểm tra hàm (chuỗi str) lấy chuỗi con str và kiểm tra xem ký tự đầu tiên và ký tự cuối cùng của nó có giống nhau không. (str [0] ==str [length-1]). Nếu đúng, hãy trả về 1.

• Hàm check_Start_End (string str, int length) lấy str và độ dài của nó làm đầu vào và trả về số lượng các chuỗi con của str bắt đầu và kết thúc bằng cùng một ký tự.

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

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

• Chúng ta sẽ nhận được tất cả các chuỗi con bằng cách sử dụng substr (i, j) với tất cả các độ dài. Chuyển từng chuỗi con để kiểm tra (). Nếu nó trả về 1, số gia tăng.

• Ở cuối cả hai số vòng lặp for sẽ có một số chuỗi con của str có cùng ký tự bắt đầu và kết thúc.

• Số lượt trả về là kết quả mong muốn.

Ví dụ

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

Đầ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 substrings with each character occurring at most k times are: 14