Số lượng tối đa các chuỗi con có độ dài K bao gồm các ký tự giống nhau trong C ++

Nhiệm vụ được giao là tìm số lượng tối đa các chuỗi con có độ dài K bao gồm các ký tự giống nhau. Cho một chuỗi s và một số nguyên khác K , chúng tôi phải đếm sự xuất hiện của các chuỗi con có kích thước K có các ký tự giống nhau.

Trong số các chuỗi con được tìm thấy, chúng ta phải chọn chuỗi con có số lượng thời gian tối đa.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào

s = ”tuuxyyuuc”, K = 2

Đầu ra

2

Giải thích

Ở đây, các chuỗi con có độ dài 2 và có các ký tự giống nhau là:“uu” và “yy” nhưng như ta thấy rằng “yy” chỉ xuất hiện 1 lần và “uu” xuất hiện 2 lần. Do đó đầu ra trở thành 2.

Đầu vào

s = “hhigggff”, K = 3

Đầu ra

1

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

• Trong hàm Max (), khởi tạo int ans =0 để lưu trữ câu trả lời cuối cùng, size =str.size () để lưu trữ kích thước của chuỗi và khai báo char c để lưu các ký tự mà chúng ta cần kiểm tra.

• Lặp lại từ j =0 đến j <26 và đặt c =‘a’ + j vì chúng ta sẽ kiểm tra từng ký tự.

• Khởi tạo biến int CurrCh =0 để lưu trữ sự xuất hiện của mảng con chứa ký tự hiện tại.

• Lặp lại từ i =0 đến i <=size - K và kiểm tra xem (str [i]! =C). Nếu vậy, sau đó thêm tiếp tục; tuyên bố.

• Khởi tạo count =0 để lưu trữ độ dài của mảng con của ký tự hiện tại.

• Tạo vòng lặp while với điều kiện (i count . Bên ngoài vòng lặp while giảm i đi 1.

• Kiểm tra xem (đếm ==K). Nếu vậy, hãy tăng CurrCh .

• Đóng vòng lặp For thứ hai và cập nhật giá trị của ans bằng cách đặt ans =max (ans, CurrCh).

• Cuối cùng đóng vòng lặp For đầu tiên và trả về ans .

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int Max(string str, int K){
   int ans = 0, size = str.size();
   char c;
   //Checking for all characters
   for (int j = 0; j < 26; j++){
      c = 'a' + j;
      //checking for current character
      int CurrCh = 0;
      for (int i = 0; i <= size - K; i++){
         if (str[i] != c)
            continue;
         //Counting the size of sub-string
         int count = 0;
         while (i < size && count != K && str[i] == c){
            i++;
            count++;
         }
         i--;
         //Increment CurrCh if sub-string has length K
         if (count == K)
            CurrCh++;
      }
      //Update ans
      ans = max(ans, CurrCh);
   }
   return ans;
}
//main function
int main(){
   string str = "tuuuxyuuu";
   int K = 3;
   cout << Max(str, K);
   return 0;
}

Đầu ra

2