สมมติว่าเรามีสตริง s เราต้องหาขนาดของสตริงย่อยที่ยาวที่สุดที่มีแต่ละสระเป็นจำนวนคู่ นั่นคือ 'a', 'e', 'i', 'o' และ 'u' ต้องปรากฏเป็นจำนวนคู่ ดังนั้นหากสตริงเป็นเหมือน “helloworld” ผลลัพธ์จะเป็น 8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0 กำหนดสองแผนที่ m และ cnt ตั้งค่า m[“00000”] :=-1
-
เก็บสระไว้ในอาร์เรย์สระ
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ s
-
x :=s[i], และ ok :=false
-
เพิ่ม cnt[x] ขึ้น 1, set temp :=สตริงว่าง
-
สำหรับ k ในช่วง 0 ถึง 4:temp :=temp + '0' + cnt[vowels[k]] mod 2
-
ถ้า m มี temp แล้ว ret :=max of ret และ i – m[temp] มิฉะนั้น m[temp] :=i
-
-
รีเทิร์น
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findTheLongestSubstring(string s) {
int ret = 0;
map <string, int> m;
map <char, int> cnt;
m["00000"] = -1;
char vowels[5] = {'a', 'e', 'i', 'o', 'u'};
for(int i = 0; i < s.size(); i++){
char x = s[i];
bool ok = false;
cnt[x]++;
string temp = "";
for(int k = 0; k < 5; k++){
temp+= ('0' + (cnt[vowels[k]] % 2));
}
if(m.count(temp)){
ret = max(ret, i - m[temp]);
}
else{
m[temp] = i;
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findTheLongestSubstring("helloworld"));
} อินพุต
“helloworld”
ผลลัพธ์
8
