จำนวนสูงสุดของสตริงย่อยที่มีความยาว K ซึ่งประกอบด้วยอักขระเดียวกันใน C++

กำหนดภารกิจคือค้นหาจำนวนสูงสุดของสตริงย่อยของความยาว K ประกอบด้วยตัวอักษรเดียวกัน กำหนดสตริง s และจำนวนเต็มอื่น K เราต้องนับการเกิดของสตริงย่อยที่มีขนาด K ที่มีตัวอักษรเหมือนกัน

จากสตริงย่อยที่พบ เราต้องเลือกสตริงย่อยที่เกิดจำนวนครั้งสูงสุด

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

อินพุต

s = ”tuuxyyuuc”, K = 2

ผลลัพธ์

2

คำอธิบาย

สตริงย่อยที่มีความยาว 2 และมีอักขระเหมือนกันคือ "uu" และ "yy" แต่จะเห็นได้ว่า "yy" เกิดขึ้นเพียง 1 ครั้งและ "uu" มี 2 ครั้ง ดังนั้นผลลัพธ์จะกลายเป็น 2

อินพุต

s = “hhigggff”, K = 3

ผลลัพธ์

1

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• ในฟังก์ชัน Max() ให้เริ่มต้น int ans =0 เพื่อเก็บคำตอบสุดท้าย size =str.size() เพื่อเก็บขนาดของสตริงและประกาศ char c เพื่อเก็บอักขระที่เราต้องตรวจสอบ

• วนจาก j =0 ถึง j <26 และใส่ c ='a' + j ตามที่เราจะตรวจสอบอักขระแต่ละตัว

• เริ่มต้นตัวแปร int CurrCh =0 เพื่อจัดเก็บการเกิดขึ้นของอาร์เรย์ย่อยที่มีอักขระปัจจุบัน

• วนจาก i =0 ถึง i <=size – K และตรวจสอบว่า (str[i] !=c) ถ้าเป็นเช่นนั้น ให้เพิ่ม ทำต่อ; คำสั่ง

• เริ่มต้นการนับ =0 เพื่อเก็บความยาวของอาร์เรย์ย่อยของอักขระปัจจุบัน

• สร้างการวนซ้ำแบบมีเงื่อนไข (i นับ . นอก while loop ลดลง 1

• ตรวจสอบว่า (นับ ==K) ถ้าเป็นเช่นนั้น ให้เพิ่ม CurrCh .

• ปิดที่สอง For loop และอัปเดตค่าของ ans โดยใส่ ans =max(ans, CurrCh)

• สุดท้ายปิด For loop แรกแล้วกลับ ans .

ตัวอย่าง

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

ผลลัพธ์

2