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

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 viết 10:55 ngày 01/10/2018

Đề 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.

Do Ngoc Anh viết 11:01 ngày 01/10/2018

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

Do Ngoc Anh viết 11:08 ngày 01/10/2018

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']

Khoa NTA viết 11:06 ngày 01/10/2018

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!

*grab popcorn* viết 10:59 ngày 01/10/2018

A post was split to a new topic: Cú pháp for lạ trong C++

Ninh Nguyễn Văn viết 11:09 ngày 01/10/2018

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 ạ?

HK boy viết 11:07 ngày 01/10/2018

Đề có nói là