Giúp giải bài tập trên codefights!

[dongocanh96 (Do Ngoc Anh)]

Trên codefights có bài như thế này:

[QUOTE]Given two strings, find the number of common characters between them.

Example

1, For s1 = “aabcc” and s2 = “adcaa”, the output should be
commonCharacterCount(s1, s2) = 3.

Strings have 3 common characters - 2 "a"s and 1 “c”.

2, For s1 = “zzzz” and s2 = “zzzzzzz”, the output should be
commonCharacterCount(s1, s2) = 4.

Strings have 4 common characters “z”.
Input/Output

[time limit] 500ms (cpp)
[input] string s1

A string consisting of lowercase latin letters a-z.

Constraints:
3 ≤ s1.length ≤ 15.

[input] string s2

A string consisting of lowercase latin letters a-z.

Constraints:
4 ≤ s2.length ≤ 15.

[output] integer[/QUOTE]

Em hiểu mang máng đề bài là tìm các kí tự chung giữa hai xâu. Ban đầu em định duyệt từ đầu tới cuối của string 1, đối với mỗi phần tử của string 1 em sẽ tìm trong string 2 xem có phần tử nào giống không, nếu tìm được một phần tử giống thì tăng biến đếm lên một đơn vị, đồng thời xóa cái kí tự ở cái vị trí vừa tìm được trong string 2 đi rồi break. Sau đó chuyển sang phần tử tiếp theo của string 1.
code của em đây

[CODE]
int commonCharacterCount(string s1, string s2){
int i, j, count = 0, n = s1.length(), m =s2.length(), t;
while(i < n){

	for(j = 0; j < m; j ++){
		if(s1[i] == s2 [j]){
			count ++;
			t = s2[j];
			s2[j] = s2[m];
			s2[m] = t;
			m --;
			break;
		}
	}
	i ++;
}
return count;

}[/CODE]
em test thì chạy ok tuy nhiên gửi lên codefights thì nó báo thời gian xử lý code vượt quá thời gian cho phép

Sau đó em đọc được trên mạng có cái thuật toán này:

Use sets and find intersection between sets to get the common characters. Use dictionaries to check the count for each common character in each string, then simply add the lowest count of each common character to a variable then return the variable.

Em hiểu là tìm tập hợp các kí tự mà hai xâu đều có, sau đó xét từng phần tử của tập hợp đó xem trong hai xâu, mỗi xâu có bao nhiêu phần tử giống chúng. Rồi trả về số phần tử chung nhỏ nhất.
ví dụ s1=aabcc, s2=adcaa thì sẽ có các phần tử chung là a và c;
s1 có 4 phần tử giống
s2 có 3 phần tử giống
=>đáp án là 3

s1=zzzz, s2=zzzzzzz thì sẽ có các phần tử chung là z;
s1 có 4 phần tử giống
s2 có 7 phần tử giống
=>đáp án là 4

Tuy nhiên em không biết thục hiện thuật toán trên như thế nào, các bác có thể chỉ cho em được không ạ. Nếu bác nào có thuật toán hay hơn thì cho em xin.
Em cám ơn

[rogp10]

Đề ntn thì chắc tính bảng tần suất kí tự cho mỗi chuỗi rồi trừ ra lấy trị tuyệt đối, cộng lại là xong

Dùng dict với set là thừa vì có a-z thôi.

[dongocanh96 (Do Ngoc Anh)]

Bác có thể giúp em cú pháp phần set với dict được không, em đọc trên cplusplus nhưng không hiểu lắm

[dongocanh96 (Do Ngoc Anh)]

Có người viết giúp em như thế này

int commonCharacterCount(string st1, string st2)
{
    int rt = 0;
    int countSt[26] = {0};
    for (char &c : st1)
    {
        countSt[c - 'a']++;
    }
    for (char &c : st2)
    {
        if (countSt[c - 'a'])
        {
            countSt[c - 'a']--;
            rt++;
        }
    }
    return rt;
}

dòng này có nghĩa là gì ạ countSt[c - 'a']

[nicklauri (Khoa NTA)]

countSt[c - 'a'] tức là đang lấy phần tử thứ (c - 'a').
Hiểu nôm na, mảng countSt gồm 26 phần tử (26 chữ cái), được đánh số từ ‘a’ (là phần tử thứ 0, ('a' - 'a')) đến ‘z’ (phần tử thứ 25, ('z' - 'a')). Khi lấy c - 'a' tức là vị trí của ký tự đó trong mảng. Ví dụ c = 'b' thì c - 'a' == 1 tức là vị trí của ‘b’ trong mảng là 1!

[Ninh_Nguyen_Van (Ninh Nguyễn Văn)]

mình test thử trường hợp này:
string st1 = “azc2z}3}**c”;
string st2 = “*az}3zb2ac”;

Hai st1,st2 này là string đúng không ạ?
Nếu vậy thì theo mình sẽ đổi countSt[c - ‘a’] thành countSt[c - ’ '] kết quả mới chính xác.
Và một cái nữa là int countSt[26] đã thực sự đúng chưa ạ?

[noname00 (HK boy)]

Đề có nói là

[input] string s1
A string consisting of lowercase latin letters a-z.

[input] string s2
A string consisting of lowercase latin letters a-z.

-> chỉ chứa các kí tự từ a đến z.

Nếu vậy thì theo mình sẽ đổi countSt[c - ‘a’] thành countSt[c - ’ '] kết quả mới chính xác.
Và một cái nữa là int countSt[26] đã thực sự đúng chưa ạ?

Code của bạn @dongocanh96 chỉ xét string với các kí tự chữ thường, nên code như vậy đúng rồi nhé.

[Ninh_Nguyen_Van (Ninh Nguyễn Văn)]

Cảm ơn bạn,
Vậy nếu mình mở rộng đề bài ra thì code sẽ phải thay đổi như mình đưa ra đúng không ạ?

[noname00 (HK boy)]

Mở rộng nữa thì có thể làm như bạn, hoặc là mở rộng đến 256 kí tự luôn (tất nhiên là sẽ có những kí tự không bao giờ được kể đến, nhưng kệ chứ )

[rogp10]

Thế chứ gì mà cứ chém to kho mặn cái gì cũng dict với chả set