C++中子字符串出现次数的最大值

假设我们有一个字符串s，我们需要找到满足以下规则的任何子字符串出现的最大次数：

  • 子字符串中不同字符的数量必须小于或等于maxLetters。
  • 子字符串的大小必须在minSize和maxSize（包含）范围内。

因此，如果输入类似于：“aababcaab”，maxLetters = 2，minSize = 3，maxSize = 4，则输出为2。子字符串“aab”在原始字符串中出现2次。这满足条件：2个唯一字符和大小为3（在minSize和maxSize之间）。

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

  • 定义一个映射m
  • 对于sz范围从minSize到maxSize
    • 创建一个映射x，创建一个临时变量temp，初始为空
    • 对于i范围从0到sz – 1
      • 将x[s[i]]增加1
      • temp := temp + s[i]
    • 对于j为0，i范围从sz到s的大小 – 1，i和j都增加1
      • 如果x的大小 <= maxLetters，则将m[temp]增加1
      • 将x[temp[0]]减少1
      • 如果x[temp[0]]为0，则从x中删除temp[0]
      • 从temp本身删除第一个和第二个元素
      • 将x[s[i]]增加1
      • temp := temp + s[i]
    • 如果x的大小 <= maxLetters，则将m[temp]增加1
  • ans := 0
  • 当映射m有一些元素时，则
    • ans := ans和第i个键值对的值中的最大值
  • 返回ans

示例（C++）

让我们来看下面的实现，以便更好地理解：

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
      unordered_map <string ,int > m;
      for(int sz = minSize; sz <= minSize; sz++){
         unordered_map <char, int> x;
         string temp ="";
         for(int i = 0; i < sz; i++){
            x[s[i]]++;
            temp += s[i];
         }
         for(int j = 0, i = sz; i < s.size(); i++, j++){
            if(x.size() <= maxLetters){
               m[temp]++;
            }
            x[temp[0]]--;
            if(x[temp[0]] == 0)x.erase(temp[0]);
            temp.erase(temp.begin(),temp.begin() + 1);
            x[s[i]]++;
            temp += s[i];
         }
         if(x.size() <= maxLetters){
            m[temp]++;
         }
      }
      int ans = 0;
      unordered_map <string ,int > :: iterator i = m.begin();
      while(i != m.end()){
         ans = max (ans, i->second);
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.maxFreq("aababcaab",2,3,4));
}

输入

"aababcaab"
2
3
4

输出

2

更新于：2020年4月30日

489 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告