একটি স্ট্রিং s দেওয়া আছে। সর্বোচ্চ দৈর্ঘ্যের সাবস্ট্রিং t বের করতে হবে যাতে সেটিতে শুধু দুটি ভিন্ন ক্যারেক্টার থাকে।
যেমন, "eceba" হলে আউটপুট হবে 3, কারণ "ece" সাবস্ট্রিংটির দৈর্ঘ্য ৩ এবং এতে শুধু 'e' ও 'c' আছে।
সমাধানের ধাপগুলো (স্লাইডিং উইন্ডো):
lengthOfLongestSubstringKDistinct(s, k)ফাংশন লিখবans := 0, ম্যাপmদিয়ে ক্যারেক্টার কাউন্ট রাখবদুটি পয়েন্টার
i, jদিয়ে উইন্ডো বড় করবযখন ভিন্ন ক্যারেক্টারের সংখ্যা
kএর চেয়ে বড় হয়, তবেiবাড়িয়ে উইন্ডো ছোট করবans = max(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);
}
};
int main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
}
ইনপুট
"eceba"
আউটপুট
3
