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

สมมติว่าเรามีสตริง s เราต้องหาความยาวของ substring ยาวที่สุด t ที่มีตัวอักษรที่แตกต่างกันได้สูงสุด 2 ตัว

ตัวอย่าง: "eceba" ผลลัพธ์ = 3 เพราะ t = "ece" ความยาว 3

วิธีแก้ปัญหา (Sliding Window)

ใช้ hash map นับจำนวนตัวอักษรใน window
ขยาย window ด้วย pointer j
ถ้าตัวอักษรต่างกัน > k ให้ย่อ window ด้วย pointer i
อัปเดตค่าสูงสุดตลอดเวลา
เรียกฟังก์ชันทั่วไป lengthOfLongestSubstringKDistinct(s, 2)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int lengthOfLongestSubstringKDistinct(string s, int k){ 
        int ans = 0; 
        unordered_map<char, int> 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; 
    } 
    int lengthOfLongestSubstringTwoDistinct(string s){ 
        return lengthOfLongestSubstringKDistinct(s, 2); 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba")); 
}

ข้อมูลนำเข้า

"eceba"