ধরি আমাদের একটি স্ট্রিং আছে; আমাদের সেই সাবস্ট্রিংটির দৈর্ঘ্য বের করতে হবে যাতে সেটিতে সর্বোচ্চ k টি ভিন্ন ক্যারেক্টার থাকে।
উদাহরণস্বরূপ, s = "eceba", k = 2 হলে আউটপুট হবে 3 কারণ T = "ece" যের দৈর্ঘ্য ৩।
সমাধানের ধাপসমূহ
- ans := 0
- একটি ম্যাপ
mসংজ্ঞায়িত। - n := s.size()
- x := 0
- j = 0, i = 0; j < n; j++:
- m[s[j]]++
- যদি m[s[j]] == 1: x++
- যখন x > k এবং i <= j:
- m[s[i]]--
- যদি m[s[i]] == 0: x--
- i++
- ans = max(ans, j - i + 1)
- ans ফেরত।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
unordered_map 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 main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}
ইনপুট
"eceba", 2
আউটপুট
3
