Độ dài của mảng con dài nhất có tần suất không vượt quá K

Đề bài

Cho một mảng số nguyên nums và một số nguyên k. Tần suất của một phần tử x là số lần nó xuất hiện trong mảng. Một mảng con được gọi là "tốt" nếu tần suất của mỗi phần tử trong mảng con này không vượt quá k.

Yêu cầu: Trả về độ dài của mảng con "tốt" dài nhất của nums.

Mảng con là một dãy liên tiếp không rỗng các phần tử trong mảng.

Ví dụ 1:
Đầu vào: nums = [1,2,3,1,2,3,1,2], k = 2

Đầu ra: 6

Giải thích: Mảng con "tốt" dài nhất có thể là [1,2,3,1,2,3] vì các giá trị 1, 2 và 3 xuất hiện nhiều nhất là 2 lần trong mảng con này. Các mảng con [2,3,1,2,3,1] và [3,1,2,3,1,2] cũng là mảng con "tốt".

Ví dụ 2:
Đầu vào: nums = [1,2,1,2,1,2,1,2], k = 1

Đầu ra: 2

Giải thích: Mảng con "tốt" dài nhất có thể là [1,2] vì các giá trị 1 và 2 xuất hiện tối đa một lần trong mảng con này.

Ví dụ 3:
Đầu vào: nums = [5,5,5,5,5,5,5], k = 4

Đầu ra: 4

Giải thích: Mảng con "tốt" dài nhất có thể là [5,5,5,5] vì giá trị 5 xuất hiện tối đa 4 lần trong mảng con này.

Giải pháp:
Để giải quyết bài toán này, ta có thể sử dụng phương pháp "Cửa sổ trượt" (sliding window) kết hợp với một cấu trúc unordered_map để theo dõi tần suất của các phần tử trong mảng con hiện tại.

Cách làm

#include <iostream>
#include <unordered_map>
using namespace std;

int doDaiMangConTot(int nums[], int n, int k) {
    unordered_map<int, int> tanSo;
    int left = 0;
    int maxLength = 0;

    for (int right = 0; right < n; right++) {
        tanSo[nums[right]]++;

        // Nếu tần suất của một phần tử nào đó vượt quá k, di chuyển con trỏ left
        while (tanSo[nums[right]] > k) {
            tanSo[nums[left]]--;
            left++;
        }

        // Cập nhật độ dài tối đa của mảng con "tốt"
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    int nums[] = {1, 2, 3, 1, 2, 3, 1, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    int k = 2;

    cout << "Do dai cua mang con tot dai nhat la: " << doDaiMangConTot(nums, n, k) << endl;

    return 0;
}