สมมติว่าเราต้องการกำหนดฟังก์ชันชื่อ countUniqueChars(s) ที่จะคืนจำนวนตัวอักษรที่ไม่ซ้ำกันใน s เช่นถ้า s = "HELLOWORLD" แล้ว "H", "E", "W", "R", "D" คือตัวอักษรที่ไม่ซ้ำเพราะปรากฏครั้งเดียว ดังนั้น countUniqueChars(s) = 5
ในโจทย์นี้ กำหนดสตริง s เราต้องหาผลรวมของ countUniqueChars(t) โดยที่ t เป็นสตริงย่อยของ s (สตริงย่อยบางส่วนอาจซ้ำกัน จึงต้องนับซ้ำด้วย)
เนื่องจากคำตอบอาจใหญ่มาก จึงคืนคำตอบแบบโมดูลอ 10^9+7
เช่น หากอินพุตคือ "HELLOWORLD" เอาต์พุตจะเป็น 128
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอน −
กำหนดฟังก์ชัน add() รับ a, b คืน (a mod m) + (b mod m)
กำหนดฟังก์ชัน mul() รับ a, b คืน (a mod m) * (b mod m)
จากเมธอดหลัก n := ขนาด s, ans := 0
สร้างอาร์เรย์ cnt ขนาด 26
วนลูป i := 0 ถึง n-1 เก็บดัชนีของแต่ละตัวอักษรใน cnt
วนลูป i := 0 ถึง 25 เพิ่ม n เข้า cnt[i] คำนวณส่วนร่วมของแต่ละช่วง
คืนค่า ans
ลองดูการนำไปใช้ต่อไปนี้ −
ตัวอย่าง
#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"));
}
อินพุต
"HELLOWORLD"
เอาต์พุต
128
