ধরুন আমাদের একটি স্ট্রিং আছে; আমাদের দীর্ঘতম সাবস্ট্রিং T-এর দৈর্ঘ্য গণনা করতে হবে যাতে সর্বাধিক k স্বতন্ত্র অক্ষর থাকে৷
সুতরাং, যদি ইনপুটটি s ="eceba", k =2 এর মত হয়, তাহলে আউটপুট হবে 3 যেহেতু T হল "ece" যার দৈর্ঘ্য 3।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=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 দ্বারা বাড়ান)
-
-
উত্তর :=সর্বাধিক উত্তর এবং (j - i + 1)
-
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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;
}
};
main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
} ইনপুট
"eceba", 2
আউটপুট
3
