C ++中具有最多K个不同字符的最长子字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串；我们必须计算包含最多k个不同字符的最长子字符串T的长度。

因此，如果输入像s =“ eceba”，k = 2，则输出将为3，因为T为“ ece”，其长度为3。

为了解决这个问题，我们将遵循以下步骤-

  • 回答：= 0

  • 定义一张映射

  • n：= s的大小

  • x：= 0

  • 对于初始化j：= 0，i：= 0，当j <n时，更新（j增加1），-

    • （将m [s [i]]减1）

    • 如果m [s [i]]等于0，则-

    • （将i增加1）

    • （将x减少1）

    • （将x增加1）

    • （将m [s [j]]增加1）

    • 如果m [s [j]]与1相同，则-

    • 而（x> k并且i <= j），做-

    • ans：= 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<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

    以上是 C ++中具有最多K个不同字符的最长子字符串 的全部内容， 来源链接： utcz.com/z/348787.html

    回到顶部