Hướng dẫn giải

Bài toán yêu cầu tìm độ dài của đoạn con liên tiếp dài nhất sao cho không có phần tử nào trùng lặp. Ta áp dụng kỹ thuật Sliding Window (hoặc Two Pointers) kết hợp cấu trúc dữ liệu Map để lưu vị trí xuất hiện gần nhất của từng phần tử:

1. Duy trì hai con trỏ l và r đại diện cho cửa sổ hiện tại \([l, r]\).
2. Di chuyển con trỏ r từ \(0\) đến \(N - 1\). Với mỗi phần tử \(a[r]\):
   • Nếu \(a[r]\) đã từng xuất hiện trước đó tại vị trí pos[a[r]] và vị trí đó \(\ge l\), ta phải co cửa sổ lại bằng cách dịch con trỏ trái: l = pos[a[r]] + 1.
   • Cập nhật vị trí xuất hiện mới nhất của \(a[r]\) là r.
   • Độ dài của đoạn con không trùng lặp kết thúc tại r là \(r - l + 1\). Cập nhật độ dài cực đại tìm được.

Độ phức tạp thời gian: \(O(N \log N)\) nếu dùng std::map hoặc \(O(N)\) trung bình nếu dùng std::unordered_map.

Mã nguồn C++ mẫu

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // pos[x] lưu vị trí xuất hiện gần nhất của phần tử x
    unordered_map<int, int> pos;
    int max_len = 0;
    int l = 0;

    for (int r = 0; r < n; r++) {
        if (pos.count(a[r])) {
            // Dịch con trỏ trái để đảm bảo không chứa phần tử lặp
            l = max(l, pos[a[r]] + 1);
        }
        pos[a[r]] = r;
        max_len = max(max_len, r - l + 1);
    }

    cout << max_len << "\n";
    return 0;
}