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