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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告