Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Số lượng tối đa xâu con độ dài K cùng ký tự trong C++

Nhiệm vụ: tìm số lượng tối đa các xâu con độ dài K gồm các ký tự giống nhau. Cho xâu s và số nguyên K, đếm số lần xuất hiện của xâu con độ dài K toàn ký tự giống nhau. Chọn xâu con xuất hiện nhiều nhất.

Ví dụ 1

Đầu vào** –

s = "tuuxyyuuc", K = 2

Đầu ra** – 2

Giải thích** – Xâu con độ dài 2 cùng ký tự: "uu", "yy". "yy" xuất hiện 1 lần, "uu" xuất hiện 2 lần → kết quả 2.

Ví dụ 2

Đầu vào** –

s = "hhigggff", K = 3

Đầu ra** – 1

Phương pháp

  • Duyệt 26 chữ cái 'a'..'z'.
  • Với mỗi ký tự c, quét xâu tìm các đoạn liên tiếp của c độ dài ≥ K.
  • Mỗi đoạn độ dài L cho ra floor(L/K) xâu con độ dài K không chồng lấn.
  • Tổng cho ký tự c, lấy max trên 26 ký tự.

Ví dụ

#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;
            int count = 0;
            while (i < size && count != K && str[i] == c) {
                i++; count++;
            }
            i--;
            if (count == K) CurrCh++;
        }
        ans = max(ans, CurrCh);
    }
    return ans;
}

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

Đầu ra

2