Chuỗi con dài nhất với tối đa K ký tự riêng biệt trong C ++

Giả sử chúng ta có một chuỗi; chúng ta phải tính độ dài của chuỗi con dài nhất T chứa nhiều nhất k ký tự khác nhau.

Vì vậy, nếu đầu vào là s =​​"eceba", k =2, thì đầu ra sẽ là 3 vì T là "ece" có độ dài của nó là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0

• Xác định một bản đồ m

• n:=kích thước của s

• x:=0

• để khởi tạo j:=0, i:=0, khi j

  • (tăng m [s [j]] lên 1)

  • nếu m [s [j]] giống với 1 thì -

    • (tăng x 1)

  • while (x> k và i <=j), do -

    • (giảm m [s [i]] đi 1)

    • nếu m [s [i]] bằng 0 thì -

      • (giảm x đi 1)

    • (tăng i lên 1)

  • ans:=tối đa ans và (j - i + 1)

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

"eceba", 2

Đầu ra

3