Chuỗi con dài nhất có nhiều nhất hai ký tự riêng biệt trong C ++

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

Vì vậy, nếu đầu vào là "eceba", thì đầu ra sẽ là 3 vì t là "ece" với độ 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 -

• Xác định một hàm lengthOfLongestSubstringKDistinct (), điều này sẽ nhận s, k,

• 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 tôi lên 1)

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

• trả lại ans

• Từ phương thức chính, hãy làm như sau

• return lengthOfLongestSubstringKDistinct (s, 2)

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;
   }
   int lengthOfLongestSubstringTwoDistinct(string s){
      return lengthOfLongestSubstringKDistinct(s, 2);
   }
};
main(){
   Solution ob;
   cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
}

Đầu vào

"eceba"

Đầu ra

3