ধরুন আমাদের একটি স্ট্রিং s আছে; আমাদের সবচেয়ে দীর্ঘতম সাবস্ট্রিং t এর দৈর্ঘ্য খুঁজে বের করতে হবে যাতে সর্বাধিক 2টি স্বতন্ত্র অক্ষর রয়েছে।
সুতরাং, যদি ইনপুটটি "eceba" এর মত হয়, তাহলে আউটপুট হবে 3 যেহেতু t হল "ece" যার দৈর্ঘ্য 3।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন lengthOfLongestSubstringKDistinct(), এর জন্য s, k,
লাগবে -
উত্তর :=0
-
একটি মানচিত্র m
সংজ্ঞায়িত করুন -
n :=s এর আকার, x :=0
-
আরম্ভ করার জন্য j :=0, i :=0, যখন j
-
(m[s[j]] 1 দ্বারা বৃদ্ধি করুন)
-
যদি m[s[j]] 1 এর সমান হয়, তাহলে −
-
(x 1 দ্বারা বাড়ান)
-
-
যখন (x> k এবং i <=j), −
করুন-
(m[s[i]] 1 দ্বারা হ্রাস করুন)
-
যদি m[s[i]] 0 এর সমান হয়, তাহলে −
-
(x 1 দ্বারা কমিয়ে দিন)
-
-
(i 1 দ্বারা বাড়ান)
-
-
ans :=সর্বাধিক উত্তর এবং j - i + 1
-
-
উত্তর ফেরত দিন
-
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
-
ফেরত lengthOfLongestSubstringKDistinct(s, 2)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k){
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
int lengthOfLongestSubstringTwoDistinct(string s){
return lengthOfLongestSubstringKDistinct(s, 2);
}
};
main(){
Solution ob;
cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
} ইনপুট
"eceba"
আউটপুট
3
