C++ में बजट के भीतर समान सबस्ट्रिंग प्राप्त करें

मान लीजिए हमने समान लंबाई के दो तार s और t दिए हैं। हम s को t में बदलना चाहते हैं। s के i-वें वर्ण को t के i-वें वर्ण में बदलने से लागत निर्धारित होगी |s[i] - t[i]| अर्थात्, वर्णों के ASCII मानों के बीच पूर्ण अंतर। हमने एक पूर्णांक maxCost भी दिया है। हमें s के एक विकल्प की अधिकतम लंबाई ज्ञात करनी है जिसे अधिकतम लागत से कम या उसके बराबर लागत के साथ t के संगत विकल्प के रूप में बदला जा सकता है।

इसलिए यदि इनपुट s ="abcd" और t ="bcdf" जैसा है, तो अधिकतम लागत 3 होगी, ऐसा इसलिए है क्योंकि s में "abc" को "bcd" में परिवर्तित किया जा सकता है, जिसकी लागत 3 होगी, फिर आउटपुट 3 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• जे:=0, योग:=0 और सेवानिवृत्त:=0

• मेरे लिए 0 से न्यूनतम s और t आकार के बीच

  • योग में वृद्धि |s[i] - t[i]|

  • जबकि योग> अधिकतम लागत

    • योग में कमी |s[i] - t[i]|

    • j को 1 से बढ़ाएँ

  • 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