C ++中最长的重复字符替换

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

假设我们给出了一个仅包含大写字母的字符串s，那么我们最多可以对该字符串执行k次操作。在一个操作中，我们可以选择字符串的任何字符并将其更改为任何其他大写字母。我们必须找到最长的子字符串的长度，该子字符串包含执行上述操作后可以获得的所有重复字母。因此，如果输入类似：“ ABAB”且k = 2，则输出将为4。这是因为两个“ A”与两个“ B”，反之亦然。

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

  • maxCount：= 0，ans：= 0和n：=字符串s的大小

  • 制作一个大小为26的数组cnt，并且j：= 0

  • 对于我：= 0至n – 1

    • 减少cnt [s [j] –'A']

    • 将j增加1

    • 将cnt [s [i] –'A']增加1

    • maxCount：= maxCount的最大值，count [s [i] –'A']

    • 当j <= i和i – j + 1 – maxCount> k时，

    • ans：= ans的最大值，i – j + 1

    • 返回ans

    例子（C ++）

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
    public:
       int characterReplacement(string s, int k) {
          int maxCount = 0;
          int ans = 0;
          int n = s.size();
          vector <int> cnt(26);
          int j = 0;
          for(int i = 0; i < n; i++){
             cnt[s[i] - 'A']++;
             maxCount = max(maxCount, cnt[s[i] - 'A']);
             while(j <= i && i - j + 1 - maxCount > k){
                --cnt[s[j] - 'A'];
                j++;
             }
             ans = max(ans, i - j + 1);
          }
          return ans;
       }
    };
    main(){
       Solution ob;
       cout << ob.characterReplacement("ABAB", 2);
    }

    输入值

    "ABAB"
    2

    输出结果

    4

    以上是 C ++中最长的重复字符替换 的全部内容， 来源链接： utcz.com/z/330943.html

    回到顶部