สตริงย่อยที่ยาวที่สุดซึ่งมีตัวอักษรต่างกันสูงสุด K ตัวใน C++

สมมติว่าเรามีสตริง เราต้องคำนวณความยาวของสตริงย่อยที่ยาวที่สุด T ที่มีตัวอักษรที่แตกต่างกันไม่เกิน k ตัว

เช่น ถ้าอินพุตคือ s = "eceba", k = 2 ผลลัพธ์จะเป็น 3 เพราะ T คือ "ece" ซึ่งมีความยาว 3

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

ans := 0
สร้าง map m นับตัวอักษรใน window
n := ความยาว s, x := 0 (จำนวนตัวอักษรที่ต่างกันใน window)
ใช้ two pointers i, j: ขยาย j เพิ่ม m[s[j]] ถ้า m[s[j]]==1 เพิ่ม x; while x > k: ลด m[s[i]] ถ้าเป็น 0 ลด x; i++; อัพเดท ans = max(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 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

สตริงย่อยที่ยาวที่สุดซึ่งมีตัวอักษรต่างกันสูงสุด K ตัวใน C++

ตัวอย่าง

อินพุต

เอาต์พุต