ধরুন আমরা countUniqueChars(s) নামক একটি ফাংশন সংজ্ঞায়িত করতে চাই যা s-এ অনন্য অক্ষরের সংখ্যা প্রদান করবে, তাই যদি s ="HELLOWORLD" তাহলে "H", "E", "W", "R", "D" হল অনন্য অক্ষর যেহেতু সেগুলি 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
এর আকার -
উত্তর :=0
-
26 আকারের একটি অ্যারে cnt সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=0, যখন i
-
x :=s[i]
-
যদি cnt[x - 'A'] এর আকার 0 এর সমান হয়, তাহলে −
-
cnt[x - 'A']
এর শেষে -1 সন্নিবেশ করুন
-
-
cnt[x - 'A']
এর শেষে i ঢোকান
-
-
আরম্ভ করার জন্য i :=0, যখন i <26, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
যদি cnt[i] এর আকার 0 এর সমান হয়, তাহলে −
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
cnt[i]
এর শেষে n সন্নিবেশ করান -
j শুরু করার জন্য :=1, যখন j
-
temp :=mul(cnt[i, j] - cnt[i, j - 1], cnt[i, j + 1] - cnt[i, j])
-
ans :=add(ans, temp)
-
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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