মান লিজিয়ে আমাদের একই দৈর্ঘ্যের দুটি স্ট্রিং s এবং t দেওয়া আছে। আমরা s কে t এ পরিবর্তন করতে চাই। s-এর i-তম ক্যারেক্টারকে t-এর i-তম ক্যারেক্টারে পরিবর্তন করার খরচ হবে |s[i] - t[i]| অর্থাৎ ASCII ভ্যালুর পরম পার্থক্য। আমাদের একটি integer maxCost ও দেওয়া আছে। আমাদের s-এর এমন সর্বোচ্চ দৈর্ঘ্যের সাবস্ট্রিং খুঁজে বের করতে হবে যা t-এর সংশ্লিষ্ট সাবস্ট্রিং-এ পরিবর্তন করা যায় এবং dessen খরচ maxCost-এর চেয়ে কম বা সমান।
উদাহরণস্বরূপ, যদি ইনপুট হয় s = "abcd" এবং t = "bcdf", তখন maxCost হবে 3, কারণ s-এর "abc" কে "bcd" এ পরিবর্তন করতে খরচ 3, তাই আউটপুট হবে 3।
সমাধানের ধাপসমূহ
- j := 0, sum := 0 এবং ret := 0
- for i in range 0 to minimum of s and t sizes:
- sum বাড়ান |s[i] – t[i]| দিয়ে
- while sum > maxCost:
- sum কমান |s[j] – t[j]| দিয়ে
- j বাড়ান 1 দিয়ে
- ret := max of ret and (i – j + 1)
- ret রিটার্ন করুন
উদাহরণ (C++)
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন -
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int j = 0;
int sum = 0;
int ret = 0;
for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
sum += abs(s[i] - t[i]);
while(sum > maxCost){
sum -= abs(s[j] - t[j]);
j++;
}
ret = max(ret, i - j + 1);
}
return ret;
}
};
ইনপুট
"abcd" "bcdf" 3
আউটপুট
3
