สมมติว่าเรามีสตริง เราต้องคำนวณความยาวของสตริงย่อยที่ยาวที่สุด T ที่มีอักขระต่างกันไม่เกิน k ตัว
ดังนั้น หากอินพุตเป็น s ="eceba", k =2 เอาต์พุตจะเป็น 3 เนื่องจาก T คือ "ece" ซึ่งมีความยาว 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ตอบ :=0
-
กำหนดหนึ่งแผนที่ m
-
n :=ขนาดของ s
-
x :=0
-
สำหรับการเริ่มต้น j :=0, i :=0, เมื่อ j
-
(เพิ่ม m[s[j]] ขึ้น 1)
-
ถ้า m[s[j]] เหมือนกับ 1 แล้ว −
-
(เพิ่ม x ขึ้น 1)
-
-
ในขณะที่ (x> k และ i <=j) ทำ -
-
(ลด m[s[i]] ลง 1)
-
ถ้า m[s[i]] เท่ากับ 0 แล้ว −
-
(ลดลง x 1)
-
-
(เพิ่ม i ขึ้น 1)
-
-
ans :=สูงสุดของ ans และ (j - i + 1)
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
}
};
main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
} อินพุต
"eceba", 2
ผลลัพธ์
3
