मान लीजिए हमारे पास समान लंबाई के दो स्ट्रिंग्स s और t दिए गए हैं। हम s को t में बदलना चाहते हैं। s के i-वें कैरेक्टर को t के i-वें कैरेक्टर में बदलने का खर्च |s[i] - t[i]| होगा, यानी दोनों कैरेक्टर्स के ASCII वैल्यूज़ का एब्सोल्यूट डिफरेंस। हमें एक इंटीजर maxCost भी दिया गया है। हमें s के उस सबस्ट्रिंग की अधिकतम लंबाई ढूंढनी है जिसे maxCost से कम या बराबर खर्च में t के करेसपॉन्डिंग सबस्ट्रिंग जैसा बनाया जा सके।
उदाहरण के लिए, अगर इनपुट है s = "abcd" और t = "bcdf", तो maxCost 3 होगा, क्योंकि s में "abc" को "bcd" में बदलने का खर्च 3 आएगा, तो आउटपुट 3 होगा।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
j := 0, sum := 0 और ret := 0
i को 0 से min(s.size(), t.size()) तक लूप करें:
sum को |s[i] - t[i]| से बढ़ाएं
जब तक sum > maxCost:
sum को |s[j] - t[j]| से घटाएं
j को 1 से बढ़ाएं
ret := max(ret, 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