Elearning CodePath – CTP Online Judge

Dãy Con Dài Nhất với Tần suất

MAXSEQ

🟢 Medium #Two Pointers #Sliding Window

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_N)$.

Yêu cầu: Tìm độ dài lớn nhất của một **dãy con liên tiếp** (subarray) $A[i..j]$ sao cho **mỗi giá trị** trong dãy con đó xuất hiện **không quá $K$ lần**.

Gọi $Count(x, A[i..j])$ là số lần giá trị $x$ xuất hiện trong dãy con $A[i..j]$.
$\text{Tìm } \max(j - i + 1) \text{ sao cho } \forall x, Count(x, A[i..j]) \le K$

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `MAXSEQ.INP` gồm:

* **Dòng 1:** Hai số nguyên dương $N$ và $K$, cách nhau một khoảng trắng. $N$ là độ dài dãy, $K$ là giới hạn tần suất.
* **Dòng 2:** $N$ số nguyên $A_1, A_2, \dots, A_N$ (các phần tử của dãy), cách nhau một khoảng trắng.

**Giới hạn (Ràng buộc):**
$*1 \le N \le 10^5 \$
$*1 \le K \le N $
$*1 \le A_i \le 10^9$

---

### 📤 Định dạng Đầu ra

Ghi ra file `MAXSEQ.OUT` một số nguyên duy nhất là độ dài của dãy con dài nhất tìm được.

---

### ✨ Ví dụ

| Input (`MAXSEQ.INP`) | Output (`MAXSEQ.OUT`) |
| :--- | :--- |
| `5 2` <br> `1 1 1 2 2` | `4` |

---

### 🧪 Giải thích Ví dụ

Cho $N=5$, $K=2$. Dãy $A = [1, 1, 1, 2, 2]$.

* Dãy con $\{1, 1, 2, 2\}$ (dài 4): Tần suất của 1 là 2, tần suất của 2 là 2. $2 \le K=2$. $\implies$ **Hợp lệ**.
* Dãy con $\{1, 1, 1, 2\}$ (dài 4): Tần suất của 1 là 3. $3 > K=2$. $\implies$ **Không hợp lệ**.
* Độ dài tối đa là 4.

---

### 💡 Gợi ý thuật toán

Sử dụng kỹ thuật **Cửa sổ Trượt Hai Con Trỏ (Two Pointers / Sliding Window)** với độ phức tạp $O(N)$.

✅ Đã AC: 6 / 8 submissions