Editorial for countstr: Truy vấn trong chuỗi

Hiểu bài toán

Cho xâu ký tự S chỉ gồm các chữ cái thường (a-z). Yêu cầu đếm số cặp chỉ số (l, r) sao cho: 1) S[l] != S[r]; 2) S[l] không xuất hiện ở bất kỳ vị trí nào giữa l và r; 3) S[r] không xuất hiện ở bất kỳ vị trí nào giữa l và r. Nói cách khác, S[l] và S[r] là hai ký tự khác nhau và chúng là lần xuất hiện đầu tiên và cuối cùng liên tiếp của các ký tự đó trong đoạn [l, r].

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

Cách Brute Force

#include <bits/stdc++.h>
#define ll long long

using namespace std;
string s;
ll ans=0;
int main()
{
    cin>>s;
    for(int i=0;i<s.size();i++){
        vector<ll> cx(255,0);
        ll vt=-1;
        for(int j=i;j<s.size();j++){
            cx[s[j]]++;
            if(cx[s[j]]==2){
                break;
            }
            vt=j;
        }
        ans+=vt-i;
    }
    cout<<ans;
    return 0;
}

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

Duyệt qua mỗi vị trí i làm l. Với mỗi i, duyệt sang phải để tìm r. Dừng lại ngay khi gặp ký tự thứ hai của bất kỳ ký tự nào (kể cả S[i]). Khi đó, tất cả các vị trí j từ i+1 đến vị trí cuối cùng có thể (trước khi dừng) đều là r hợp lệ. Số lượng r hợp lệ bằng (vt - i). Cụ thể, từ i đến vt, mỗi ký tự chỉ xuất hiện đúng 1 lần, nên với mọi j > i, S[i] không nằm giữa (i, j) và S[j] cũng không nằm giữa (i, j). Do đó, chỉ cần kiểm tra S[i] != S[j] là đủ. Độ phức tạp là O(N^2) do lặp kép, phù hợp với N nhỏ.

Cách Optimized O(N)

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
using namespace std;

string s;
int pre[30];

void hihihah () {
    cin >> s;
    int n = s.size();
    s = " " + s;

    int ans = 0;

    for (int i = 1; i <= n; i ++) {
        int cur = s[i] - 'a';
        for (int j = 0; j < 26; j ++)
            if (pre[j] > 0 && pre[j] > pre[cur]) {
                ans ++;
            }
        pre[cur] = i;
    }

    cout << ans;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    hihihah ();
    return 0;
}

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

Cách tiếp cận này dựa trên quan sát khi duyệt qua các ký tự từ trái sang phải. Với mỗi ký tự tại vị trí i (đóng vai trò là r), ta cần đếm số lượng các ký tự khác có lần xuất hiện gần nhất trước i mà chưa bị 'phá vỡ' bởi sự xuất hiện của chính nó ở giữa.

Giả sử ta duyệt đến vị trí i. Gọi pre[c] là vị trí xuất hiện gần nhất của ký tự c trước i. Để (l, r) = (l, i) hợp lệ với l < i, ta cần:

1. S[i] != S[l] (tức là l không thuộc ký tự hiện tại).
2. S[l] không xuất hiện giữa l và i. Điều này đúng nếu pre[S[l]] = l (vì pre[S[l]] là vị trí gần nhất trước i).
3. S[i] không xuất hiện giữa l và i. Điều này đúng nếu pre[S[i]] < l (vì pre[S[i]] là vị trí gần nhất của S[i] trước i, nếu nó nằm sau l thì S[i] đã xuất hiện ở giữa).

Tại vị trí i, ta cập nhật pre[S[i]] = i. Với các ký tự c khác S[i], ta đếm số lượng pre[c] > pre[S[i]]. Logic: Nếu pre[c] > pre[S[i]], có nghĩa là lần xuất hiện gần nhất của c nằm sau lần xuất hiện gần nhất của S[i]. Khi đó, với l = pre[c], ta có pre[S[i]] < l < i. Điều này thỏa mãn cả 3 điều kiện:

• S[l] = c != S[i]
• pre[c] = l (S[l] không xuất hiện giữa l và i)
• pre[S[i]] < l (S[i] không xuất hiện giữa l và i)

Độ phức tạp là O(26*N) do với mỗi ký tự, ta lặp qua 26 ký tự trong bảng pre.

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

Bài học kinh nghiệm

• Điều kiện 'S[l] không nằm giữa l và r' và 'S[r] không nằm giữa l và r' có thể được suy简化 thành: S[l] là lần xuất hiện cuối cùng của ký tự đó trước r, và S[r] là lần xuất hiện tiếp theo của ký tự đó sau l. Điều này dẫn đến hai cách tiếp cận: (1) Duyệt l và tìm giới hạn r (không gặp ký tự lặp lại), hoặc (2) Duyệt r và xét các l thỏa mãn điều kiện.
• Trong cách tiếp cận O(N), ta chú ý đến thứ tự của các lần xuất hiện. Nếu một ký tự A xuất hiện sau ký tự B (lần xuất hiện gần nhất trước i), thì khi xét r tại i, cặp (lần xuất hiện gần nhất của A, i) sẽ hợp lệ, nhưng cặp (lần xuất hiện gần nhất của B, i) thì không.
• Bài toán có thể coi là đếm số cặp (l, r) sao cho đoạn con S[l...r] chứa toàn các ký tự khác nhau và S[l], S[r] là hai đầu mút.

Lỗi thường gặp

• Quên kiểm tra điều kiện S[l] != S[r] trong khi viết code. Tuy nhiên, trong logic O(N) (cách 2), điều này được đảm bảo vì ta chỉ so sánh các ký tự khác nhau (pre[j] với pre[cur]). Trong Brute Force, điều kiện này được kiểm tra trực tiếp.
• Lỗi chỉ số mảng hoặc xử lý edge case với xâu rỗng hoặc độ dài 2. Trong cách 2, việc thêm dấu cách vào đầu xâu (s = " " + s) và duyệt từ 1 đến n giúp tránh lỗi off-by-one và xử lý pre[...] khởi tạo bằng 0 dễ dàng hơn.
• Hiểu sai điều kiện 'không nằm giữa'. Trong Brute Force, việc dừng vòng lặp ngay khi gặp ký tự lặp lại là chính xác. Nếu không dừng mà chỉ đánh dấu, ta có thể đếm sai.
• Trong cách 2, cần đảm bảo chỉ đếm các ký tự đã xuất hiện trước đó (pre[j] > 0) và pre[j] > pre[cur]. Việc thiếu điều kiện pre[j] > 0 có thể gây lỗi nếu pre mặc định là 0.
• Các ký tự không xuất hiện trước i có pre là 0. Vì ta chỉ quan tâm đến các l < i đã xuất hiện, nên điều kiện pre[j] > 0 là bắt buộc.