ধরুন s হলো "abcdefghijklmnopqrstuvwxyz" স্ট্রিং-এর অসীম র্যাপঅরাউন্ড সংস্করণ, তাহলে s-এর মান দেখাবে এমন − "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."।
আমাদের কাছে আরেকটি স্ট্রিং p আছে। আমাদের কাজ হলো p-এর কতগুলো ইউনিক নন-এম্পটি সাবস্ট্রিং s-এ উপস্থিত আছে তা বের করা। নির্দিষ্টভাবে, ইনপুট হলো স্ট্রিং p এবং আউটপুট হবে p-এর আলাদা নন-এম্পটি সাবস্ট্রিংয়ের সংখ্যা s স্ট্রিং-এ।
তাই যদি ইনপুট হয় “zab” তবে আউটপুট হবে ৬। স্ট্রিং “zab”-এর s-এ ৬টি সাবস্ট্রিং রয়েছে: “z”, “a”, “b”, “za”, “ab”, “zab”।
এটি সমাধান করার জন্য নিচের ধাপগুলো ফলো করব:
সাইজ ২৬-এর একটি dp অ্যারে তৈরি করুন, x := 0 সেট করুন
i = 0 থেকে p-এর সাইজ পর্যন্ত লুপ চালান
যদি i > 0 এবং (p[i] – p[i – 1] == 1 অথবা p[i – 1] – p[i] == 25), তবে x ১ বাড়ান, অন্যথায় x := 1 সেট করুন
dp[p[i] – 'a'র ASCII] := max(x, dp[p[i] – 'a'র ASCII])
ret := 0
i = 0 থেকে ২৫ পর্যন্ত লুপ চালান
ret := ret + dp[i]
ret রিটার্ন করুন
উদাহরণ (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
