ধরুন আমরা একই দৈর্ঘ্যের দুটি স্ট্রিং s এবং t দিয়েছি। আমরা টি পরিবর্তন করতে চাই. s-এর i-th অক্ষরকে t-এর i-তম অক্ষরে পরিবর্তন করলে খরচ হবে |s[i] - t[i]| অর্থাৎ, অক্ষরের ASCII মানের মধ্যে পরম পার্থক্য। আমরা একটি পূর্ণসংখ্যা maxCostও দিয়েছি। আমাদের s-এর একটি সাবস্ট্রিং-এর সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করতে হবে যেটিকে t-এর সংশ্লিষ্ট সাবস্ট্রিং-এর মতো পরিবর্তন করা যেতে পারে যার দাম maxCost-এর চেয়ে কম বা সমান৷
সুতরাং যদি ইনপুটটি s =“abcd” এবং t =“bcdf” এর মত হয়, তাহলে maxCost হবে 3, এর কারণ হল “abc” s-এ রূপান্তরিত করা যেতে পারে “bcd”, যার দাম হবে 3, তারপর আউটপুট 3 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
j :=0, যোগফল :=0 এবং ret :=0
-
আমি 0 থেকে সর্বনিম্ন s এবং t আকারের পরিসরে
-
যোগফল |s[i] – t[i] |
দ্বারা বৃদ্ধি করুন -
যখন যোগফল> সর্বোচ্চ মূল্য
-
যোগফল |s[i] – t[i] |
দ্বারা হ্রাস করুন -
1 দ্বারা j বাড়ান
-
-
ret :=ret এর সর্বোচ্চ এবং (i – j + 1)
-
-
রিটার্ন রিটার্ন
উদাহরণ (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
