Hiểu bài toán

Cho một chuỗi s. Tìm độ dài lớn nhất của một đoạn con liên tiếp có thể tạo thành một vòng tròn (khi các ký tự trong đoạn được nối lại với nhau) sao cho mỗi ký tự xuất hiện trong đoạn chỉ xuất hiện đúng một lần. Nói cách khác, ta cần tìm độ dài lớn nhất của một đoạn con [i, j] trong chuỗi s mà tất cả các ký tự trong đoạn này đều khác nhau. Tuy nhiên, dựa trên các giải pháp được cung cấp, bài toán thực chất yêu cầu tìm giá trị lớn nhất của (vị trí cuối cùng của ký tự X trong chuỗi - vị trí đầu tiên của ký tự X trong chuỗi + 1) trên tất cả các ký tự X có trong chuỗi. Đây là độ dài lớn nhất của một đoạn con bắt đầu từ lần xuất hiện đầu tiên của một ký tự và kết thúc tại lần xuất hiện cuối cùng của nó.

Các cách tiếp cận

Cách Hash Map (Ánh xạ ký tự)

#include <bits/stdc++.h>
using namespace std;
long long t,l,r,kq=-2e9;
map<char,long long> m;
string s;
//--------------------------------
int  main()
{
     freopen("BAI4.inp","r",stdin);
     freopen("BAI4.out","w",stdout);
     cin>>s;
     for(int i=0;i<s.size();i++) m[s[i]]=i;

     for(int i=0;i<s.size();i++) kq=max(kq,m[s[i]]-i+1);

     cout<<kq;
}

• Time Complexity: O(N log N)
• Space Complexity: O(K) (K là số ký tự khác nhau)

Sử dụng một map (hoặc bảng băm) để lưu vị trí cuối cùng của mỗi ký tự. Duyệt qua chuỗi từ đầu đến cuối, với mỗi ký tự tại vị trí i, ta lấy vị trí cuối cùng của nó từ map (giả sử là lastpos). Giá trị cần xét là lastpos - i + 1. Cập nhật giá trị lớn nhất cho đến khi kết thúc. Độ phức tạp là O(N log N) do thao tác với map.

Cách Mảng tĩnh (Cải tiến)

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

string s;
int cnt[1000], ans = 0;

int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        cnt[s[i]] = i;
    }

    for(int i = 0; i < s.size(); i++){
        ans = max(ans, cnt[s[i]] - i + 1);
    }

    cout << ans;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (Mảng kích thước cố định)

Thay vì dùng map, ta dùng một mảng kích thước cố định (ví dụ 1000 hoặc 256) để lưu vị trí cuối cùng của mỗi ký tự ASCII. Điều này giúp truy cập và cập nhật vị trí cuối cùng trong thời gian hằng số O(1). Bước đầu tiên duyệt toàn bộ chuỗi để ghi nhận vị trí cuối cùng của mỗi ký tự. Bước thứ hai duyệt lại chuỗi để tính toán độ dài đoạn con tối đa. Đây là cách hiệu quả nhất về mặt thời gian chạy.

Cách Một lượt duyệt (Một mảng)

#include <bits/stdc++.h>
#define st string
#define ioss ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rt return
#define ll long long
using namespace std;
st x;
ll ans = 0;
int main()
{
    freopen("BAI4.inp", "r", stdin);
    freopen("BAI4.out", "w", stdout);
    ioss
    cin >> x;
    vector<ll> f(27, -1);
    vector<ll> f1(27, -1);
    for(ll i = 0; i < x.size(); i ++)
    {
        if(f[x[i] - 'A'] == -1) f[x[i] - 'A'] = i;
        f1[x[i] - 'A'] = i;
    }
    for(ll i = 0; i < 26; i ++)
    {
        if(f1[i] != -1 && f[i] != -1) ans = max(ans, f1[i] - f[i] + 1);
    }
    cout << ans;
    rt 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phương pháp này sử dụng hai mảng (hoặc vector) nhỏ để lưu vị trí xuất hiện đầu tiên (f) và cuối cùng (f1) của mỗi ký tự từ 'A' đến 'Z'. Chỉ cần duyệt chuỗi một lần để điền vào hai mảng này, sau đó duyệt qua 26 ký tự để tìm giá trị max(f1[i] - f[i] + 1). Cách này tách biệt việc ghi nhận vị trí và tính toán, giúp logic rõ ràng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giảm về việc tìm khoảng cách lớn nhất giữa hai lần xuất hiện của cùng một ký tự trong chuỗi.
• Sử dụng mảng tĩnh để lưu vị trí cuối cùng của các ký tự (thay vì map) giúp tối ưu hóa thời gian chạy từ O(N log N) xuống O(N).

Lỗi thường gặp

• Cần phân biệt giữa vị trí đầu tiên và vị trí cuối cùng của một ký tự. Nếu chỉ lưu vị trí cuối cùng, ta cần đảm bảo tính toán đúng khoảng cách từ bất kỳ vị trí nào đến vị trí cuối cùng đó.
• Quên khởi tạo giá trị mặc định cho mảng lưu vị trí có thể dẫn đến lỗi logic (ví dụ tính toán sai nếu ký tự xuất hiện duy nhất một lần).