home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม C

หา Longest Substring ที่มีสระอยู่จำนวนคู่ ใน C++

สมมติเรามีสตริง s เราต้องหาขนาดของ longest substring ที่มีสระแต่ละตัว (a, e, i, o, u) อยู่จำนวนคู่ เช่นสตริง "helloworld" ผลลัพธ์คือ 8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอน −

  • ret := 0, define two maps m และ cnt, set m["00000"] := -1

  • เก็บสระไว้ใน vowels array

  • for i in range 0 to size of s

    • x := s[i], ok := false

    • เพิ่ม cnt[x] ขึ้น 1, set temp := empty string

    • for k in range 0 to 4: temp := temp + '0' + cnt[vowels[k]] mod 2

    • ถ้า m มี temp, ret := max(ret, i - m[temp]), มิฉะนั้น m[temp] := i

  • return ret

ตัวอย่าง (C++)

มาดูการนำไปใช้เพื่อเข้าใจดีขึ้น −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ret = 0;
        map  m;
        map  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"));
}

Input

"helloworld"

Output

8