Thuật toán 1: Duyệt 2 for kèm mảng đánh dấu kí tự đã dùng chưa cho mỗi lần duyệt

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

int main() {
    // Đọc và ghi file bằng freopen 
    // freopen("ROBOTCHAR.INP", "r", stdin);  
    // freopen("ROBOTCHAR.OUT", "w", stdout); 

    string s;
    cin >> s; // Nhập một chuỗi ký tự từ bàn phím

    int maxLen = 0;            // Biến lưu độ dài lớn nhất của chuỗi con không lặp ký tự
    int n = s.length();        // Độ dài chuỗi đầu vào

    // Duyệt qua từng vị trí i trong chuỗi để bắt đầu một chuỗi con
    for (int i = 0; i < n; i++) 
    {
        vector<bool> visited(26, false); // Mảng đánh dấu 26 chữ cái A-Z đã xuất hiện hay chưa
        int d = 0; // Biến đếm số ký tự khác nhau trong chuỗi con bắt đầu từ vị trí i

        // Duyệt từ vị trí i đến hết chuỗi

        for (int j = i; j < n; j++) 
        {
            if (!visited[s[j] - 'A']) // Nếu ký tự s[j] chưa xuất hiện
            {
                visited[s[j] - 'A'] = true; // Đánh dấu là đã xuất hiện
                d++;                        // Tăng số lượng ký tự khác nhau
                maxLen = max(maxLen, d);   // Cập nhật độ dài lớn nhất nếu cần
            } 
            else break; // Nếu gặp ký tự đã xuất hiện, dừng chuỗi con tại đây

        }
    }


    cout << maxLen << endl;

    return 0;
}

Thuật toán 2 : Sử dụng ý tưởng thuật toán 2 con trỏ để kiểm tra trong cửa sổ đang xét có tồn tại ký tự đang xét chưa?

📌 2. Ý tưởng cụ thể thuật toán: Sliding Window

Sliding Window (cửa sổ trượt) là một kỹ thuật dùng 2 con trỏ (left, right) để quét qua các đoạn con của chuỗi.

• left: bắt đầu của cửa sổ (vị trí đầu của đoạn con đang xét).
• right: kết thúc của cửa sổ (vị trí hiện tại đang duyệt tới).
• Duy trì cửa sổ sao cho tất cả ký tự trong đó là **không lặp.

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

int main() {
    // Mở file để đọc và ghi dữ liệu
    freopen("ROBOTCHAR.INP", "r", stdin);
    freopen("ROBOTCHAR.OUT", "w", stdout);

    string s;
    cin >> s;

    vector<int> lastPos(26, -1); // Vị trí xuất hiện gần nhất của mỗi ký tự A-Z : Từ 0-->25

    int maxLen = 0;
    int left = 0, right = 0;
    int n = s.length();

    while (right < n) 
    {
        char c = s[right];

        // Nếu c đã xuất hiện trong cửa sổ hiện tại → cần cập nhật left
        if (lastPos[c - 'A'] >= left) 
        {
            left = lastPos[c - 'A'] + 1;
        }

        // Cập nhật vị trí xuất hiện gần nhất của c

        lastPos[c - 'A'] = right;

        // Cập nhật độ dài lớn nhất của chuỗi con không lặp

        maxLen = max(maxLen, right - left + 1);

        // Di chuyển con trỏ phải sang ký tự tiếp theo

        right++;
    }

    cout << maxLen << endl;
    return 0;
}

📋 Bảng mô tả thuật toán Sliding Window với chuỗi "ACBCA"

✅ Kết luận:

• Độ dài chuỗi con dài nhất không lặp ký tự là 3.
• Các chuỗi con hợp lệ dài nhất: "CBA" hoặc "BCA".