จำนวนครั้งสูงสุดของซับสตริงใน C++

สมมติว่าเรามีสตริง s เราต้องหาจำนวนครั้งสูงสุดของซับสตริงใดซับสตริงหนึ่งที่สอดคล้องกับเงื่อนไข:

• จำนวนตัวอักษรที่แตกต่างกันในซับสตริงต้องน้อยกว่าหรือเท่ากับ maxLetters
• ขนาดของซับสตริงต้องอยู่ในช่วง minSize ถึง maxSize รวม

ตัวอย่าง: "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4 ผลลัพธ์: 2 เพราะซับสตริง "aab" ปรากฏ 2 ครั้ง ตรงตามเงื่อนไข (2 ตัวอักษรที่แตกต่างกัน ขนาด 3)

ขั้นตอนการแก้ปัญหา (Sliding Window)

• กำหนดแผนที่ 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 ลบ temp[0] ออกจาก x
    • ลบตัวแรกและตัวที่สองของ temp ออกจาก temp เอง
    • เพิ่ม x[s[i]] ขึ้น 1
    • temp := temp + s[i]
  • ถ้า ขนาดของ x <= maxLetters เพิ่ม m[temp] ขึ้น 1
• ans := 0
• วนลูปผ่านแผนที่ m หาค่า max ของค่าทุกคู่
• คืนค่า 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;
    }
};

int main() {
    Solution ob;
    cout << (ob.maxFreq("aababcaab", 2, 3, 4));
}

อินพุต

"aababcaab" 2 3 4

เอาต์พุต

2