ধরুন আমাদের কাছে "abcdefghijklmnopqrstuvwxyz" এর অসীম মোড়কের স্ট্রিং s আছে, তাহলে s এর মান এইরকম হবে − "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvcdwxyz"... পি>
এখন আমরা আরেকটি স্ট্রিং পি আছে. আমাদের কাজ হল p-এর কতগুলি অনন্য নন-খালি সাবস্ট্রিং s-এ উপস্থিত রয়েছে তা খুঁজে বের করা। বিশেষ করে, আমাদের ইনপুট হল p স্ট্রিং এবং আমাদের স্ট্রিং s-এ p এর বিভিন্ন অ-খালি সাবস্ট্রিংগুলির সংখ্যা আউটপুট করতে হবে।
সুতরাং ইনপুট যদি “zab” এর মত হয় তাহলে আউটপুট হবে 6। স্ট্রিং “z”, “a”, “b”, “za”, “ab”, “zab” এর মধ্যে 6 টি সাবস্ট্রিং আছে। স্ট্রিং s
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
26 আকারের একটি অ্যারে ডিপি তৈরি করুন, x :=0
সেট করুন -
আমি 0 থেকে p
এর পরিসরে-
যদি i> 0 এবং (p[i] – p[i – 1] হয় 1 বা p[i – 1] – p[i] হয় 25), তাহলে x বাড়ান 1, অন্যথায় x :=1
-
dp[p[i] – ASCII of 'a'] :=সর্বাধিক (x, dp[p[i] - 'a'] এর ASCII)
-
-
ret :=0
-
আমি 0 থেকে 25 রেঞ্জের জন্য
-
ret :=ret + dp[i]
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSubstringInWraproundString(string p) {
vector <int> dp(26);
int x = 0;
for(int i = 0; i < p.size(); i++){
if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
x++;
}
else x = 1;
dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
}
int ret = 0;
for(int i = 0; i < 26; i++){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findSubstringInWraproundString("zab"));
} ইনপুট
"zab"
আউটপুট
6
