Hiểu bài toán

Cho hai chuỗi x và y chỉ chứa các ký tự thường từ 'a' đến 'z'. Nhiệm vụ của bạn là tìm và in ra các ký tự xuất hiện trong cả hai chuỗi. Các ký tự phải được in ra theo thứ tự từ điển tăng dần, mỗi ký tự trên một dòng. Ví dụ, nếu x = "abc" và y = "cde", kết quả là "c".

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

Cách Dùng set để loại bỏ trùng lặp

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("KiTuChung.Inp","r",stdin);
    freopen("KiTuChung.Out","w",stdout);
    string x,y;cin>>x>>y;
    set<char>a;
    for(auto i:x){
        if(y.find(i)!=string::npos)a.insert(i);
    }
    for(auto i:a)cout<<i<<endl;
}

• Time Complexity: O(N * M) (vì string::find trong vòng lặp O(N) có độ phức tạp O(M)), hoặc O(N log N) nếu M nhỏ.
• Space Complexity: O(1)

Phương pháp này sử dụng một set<char> để lưu trữ các ký tự chuniq và tự động sắp xếp. Với mỗi ký tự trong chuỗi x, ta kiểm tra xem nó có tồn tại trong chuỗi y không bằng hàm y.find(i). Nếu có, ta chèn nó vào set. Cuối cùng, duyệt qua set để in ra kết quả. Cách này khá trực quan nhưng hiệu năng không tốt nếu hai chuỗi dài.

Cách Mảng đánh dấu (Boolean Array)

#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("KiTuChung.Inp","r",stdin);
freopen("KiTuChung.Out","w",stdout);
string x,y;
cin>>x>>y;
bool a[26]={0},b[26]={0};
for(char c:x)a[c-'a']=1;
for(char c:y)b[c-'a']=1;
for(int i=0;i<26;i++)
if(a[i]&&b[i])cout<<char('a'+i)<<endl;
}

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

Đây là cách hiệu quả nhất. Ta sử dụng hai mảng boolean cỡ 26 phần tử (tương ứng 26 chữ cái). Phần tử a[k] là true nếu ký tự 'a'+k có trong chuỗi x, và b[k] là true nếu nó có trong chuỗi y. Ta duyệt qua chuỗi x và y để đánh dấu. Cuối cùng, duyệt i từ 0 đến 25, nếu a[i] và b[i] đều true thì in ra ký tự tương ứng. Độ phức tạp thời gian là O(N) để điền mảng và O(1) (26 lần lặp) để in.

Cách Hash Map (Map)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("KiTuChung.Inp","r",stdin);
    freopen("KiTuChung.Out","w",stdout);
    string x,y;
    cin >> x >> y;
    map<char,long long> a,b;
    for(auto i:x) a[i]++;
    for(auto i:y){
        if(a.find(i)!=a.end()) b[i]++;
    }
    for(auto i:b) cout << i.first << "\n";
}

• Time Complexity: O(N log N + M log N)
• Space Complexity: O(1)

Sử dụng map<char, int> để đếm tần suất hoặc đánh dấu sự tồn tại. Ta duyệt qua chuỗi x để đưa các ký tự vào map a. Sau đó, duyệt chuỗi y, nếu ký tự đó đã có trong map a thì thêm vào map b (là map chứa kết quả). Map tự động sắp xếp key theo thứ tự từ điển, nên ta chỉ cần duyệt map b để in ra. Cách này chậm hơn mảng đánh dấu do chi phí log N của map.

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

Bài học kinh nghiệm

• Bài toán chỉ giới hạn 26 ký tự thường, nên giải pháp dùng mảng c cố định (size 26) là tối ưu nhất về cả thời gian và bộ nhớ.
• Thứ tự xuất hiện trong chuỗi không quan trọng, chỉ cần xuất hiện trong cả hai chuỗi.
• Ký tự in ra phải được sắp xếp theo thứ tự từ điển.

Lỗi thường gặp

• Quên kiểm tra điều kiện xuất hiện ở cả hai chuỗi, dẫn đến in ra ký tự chỉ có ở một chuỗi.
• In ra ký tự trùng lặp nếu dùng mảng đếm (count) và in ngay trong vòng lặp kiểm tra y (phải gom nhóm lại hoặc dùng set/mảng đánh dấu).
• Xử lý sai thứ tự in ra (không sắp xếp) nếu dùng các cấu trúc dữ liệu không tự động sort như hash set (unordered_set) hoặc duyệt ngẫu nhiên.