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

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

จาก sub-strings ที่พบ เราต้องเลือก sub-string ที่เกิดขึ้นมากที่สุด

ตัวอย่าง

อินพุต

s = "tuuxyyuuc", K = 2

เอาต์พุต

คำอธิบาย

Sub-strings ความยาว 2 ตัวอักษรเดียวกันคือ "uu" และ "yy" แต "yy" เกิด 1 ครั้ง ส่วน "uu" เกิด 2 ครั้ง ดังนั้นผลลัพธ์คือ 2

อินพุต

s = "hhigggff", K = 3

เอาต์พุต

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

ใน Max() เริ่มต้น int ans = 0 เก็บคำตอบ size = str.size() เก็บความยาว และ char c เก็บตัวอักษรที่ตรวจสอบ
ลูป j = 0 ถึง j < 26 ใส่ c = 'a' + j (ตรวจสอบทุกตัวอักษร)
เริ่มต้น int CurrCh = 0 เก็บจำนวน sub-array ของตัวอักษรปัจจุบัน
ลูป i = 0 ถึง i <= size - K ถ้า str[i] != c continue
เริ่มต้น count = 0 เก็บความยาว sub-array ของตัวอักษรปัจจุบัน
While loop เงื่อนไข (i < size && count != K && str[i] == c) ในลูป i++ และ count++ นอก while i--
ถ้า count == K เพิ่ม CurrCh++
ปิดลูป for ที่ 2 อัปเดต ans = max(ans, CurrCh)
ปิดลูป for ที่ 1 คืนค่า ans

ตัวอย่างโปรแกรม

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

int Max(string str, int K) {
    int ans = 0, size = str.size();
    char c;
    // ตรวจสอบทุกตัวอักษร
    for (int j = 0; j < 26; j++) {
        c = 'a' + j;
        // ตรวจสอบตัวอักษรปัจจุบัน
        int CurrCh = 0;
        for (int i = 0; i <= size - K; i++) {
            if (str[i] != c)
                continue;
            // นับความยาว sub-string
            int count = 0;
            while (i < size && count != K && str[i] == c) {
                i++;
                count++;
            }
            i--;
            // เพิ่ม CurrCh ถ้า sub-string ยาว K
            if (count == K)
                CurrCh++;
        }
        // อัปเดต ans
        ans = max(ans, CurrCh);
    }
    return ans;
}

int main() {
    string str = "tuuuxyuuu";
    int K = 3;
    cout << Max(str, K);
    return 0;
}