Giả sử chúng ta muốn định nghĩa một hàm countUniqueChars(s) trả về số ký tự duy nhất trong s, ví dụ s = "HELLOWORLD" thì "H", "E", "W", "R", "D" là các ký tự duy nhất vì chúng chỉ xuất hiện một lần, do đó countUniqueChars(s) = 5.
Bây giờ, cho một chuỗi s, chúng ta phải tìm tổng của countUniqueChars(t) với t là một chuỗi con của s. (Ở đây một số chuỗi con có thể trùng lặp nên trong trường hợp này chúng ta phải đếm cả các chuỗi con trùng lặp.)
Vì câu trả lời có thể rất lớn, chúng ta trả về kết quả modulo 10^9+7.
Ví dụ, nếu đầu vào là "HELLOWORLD", thì đầu ra sẽ là 128.
Để giải quyết bài toán, chúng ta làm theo các bước sau −
Định nghĩa hàm add(), nhận a, b,
trả về (a mod m) + (b mod m)
Định nghĩa hàm mul(), nhận a, b,
trả về (a mod m) * (b mod m)
Từ phương thức main, thực hiện như sau −
n := kích thước của s
ans := 0
Định nghĩa mảng cnt kích thước 26
for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), thực hiện −
x := s[i]
nếu kích thước của cnt[x - 'A'] bằng 0, thì −
chèn -1 vào cuối cnt[x - 'A']
chèn i vào cuối cnt[x - 'A']
for khởi tạo i := 0, khi i < 26, cập nhật (tăng i lên 1), thực hiện −
nếu kích thước của cnt[i] bằng 0, thì −
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
chèn n vào cuối cnt[i]
for khởi tạo j := 1, khi j < kích thước của cnt[i], cập nhật (tăng j lên 1), thực hiện −
temp := mul(cnt[i, j] - cnt[i, j - 1], cnt[i, j + 1] - cnt[i, j])
ans := add(ans, temp)
trả về ans
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public: lli add(lli a, lli b){ return (a % m) + (b % m); } lli mul(lli a, lli b){ return (a % m) * (b % m); } int uniqueLetterString(string s) { int n = s.size(); int ans = 0; vector<int> cnt[26]; for (int i = 0; i < n; i++) { char x = s[i]; if (cnt[x - 'A'].size() == 0) { cnt[x - 'A'].push_back(-1); } cnt[x - 'A'].push_back(i); } for (int i = 0; i < 26; i++) { if (cnt[i].size() == 0) continue; cnt[i].push_back(n); for (int j = 1; j < cnt[i].size() - 1; j++) { lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j + 1] - cnt[i][j]); ans = add(ans, temp); } } return ans; } }; main(){ Solution ob; cout << (ob.uniqueLetterString("HELLOWORLD")); } Đầu vào
"HELLOWORLD"
Đầu ra
128