Leetcode 1297. Maximum Number of Occurrences of a Substring

문제 : 1297. Maximum Number of Occurrences of a Substring

등급 : Medium

pub(self) mod first_try {
    pub struct Solution;
    impl Solution {
        pub fn max_freq(s: String, max_letters: i32, min_size: i32, max_size: i32) -> i32 {
            let s_len = s.len();
            let mut begin = 0usize;

            let mut hm = std::collections::HashMap::<&str, i32>::new();

            while begin <= s_len - min_size as usize {
                let mut cur_len = min_size as usize;
                let avail_size = (max_size as usize).min(s_len - begin);

                while cur_len <= avail_size {
                    let substring = &s[begin..begin+cur_len];
                    if Self::get_number_of_unique_characters(substring) <= max_letters {
                        if let Some(cnt) = hm.get_mut(substring) {
                            *cnt += 1;
                        }
                        else {
                            hm.insert(substring, 1);
                        }
                    }

                    cur_len += 1;
                }

                begin += 1;
            }

            let mut max_occurrences = 0i32;
            for (_, cnt) in hm {
                max_occurrences = max_occurrences.max(cnt);
            }

            max_occurrences
        }

        fn get_number_of_unique_characters(s: &str) -> i32 {
            let mut set = std::collections::BTreeSet::<char>::new();
            for c in s.chars() {
                set.insert(c);
            }

            set.len() as i32
        }

    }
}

#[cfg(test)]
mod tests {
    use crate::maximum_number_of_occurrences_of_a_substring::first_try::Solution;

    #[test]
    fn example() {
        assert_eq!(Solution::max_freq("aababcaab".to_owned(), 2, 3, 4), 2);
        assert_eq!(Solution::max_freq("aaaa".to_owned(), 1, 3, 3), 2);
        assert_eq!(Solution::max_freq("a".to_owned(), 1, 1, 1), 1);
        assert_eq!(Solution::max_freq("abcde".to_owned(), 2, 3, 3), 0);
        assert_eq!(Solution::max_freq("ljkelhjicdmmhdbahibcdhfgmkccjbmdggfflamidcmabmihckdblchdhiddcmffahmmcghlhamajmcfldmgacgfmfkaifgeljkdggfjamlecdgakblaajjakhaichjjmgfhmdckfebmmbgbfkbekakamhkgeehcbmiibcfagamhhfbgafiiekkfcbbejaclcdlfgiijbekjbhkccelgljfhlkfidgihkamfgmfddgdglifbikhmgicbgmlaifjddebcaffkedfgmgaikcmlijjlhddjamlcgiaialdmhbkddalkfhhkajajgcdjcaiaedfmlejabdlmfceijiijfbaeilbfdhcificlhmieagkkglfgdjamblmihhaeghljlhkhidjafhgadgajlkikhijekkhiahldiibhjhifmgbdjdcfhijeiemchkhkcihchjfacaddfgckickiecijkjfhffkeemcdhgegbdfhigiihdhldklaidjjjeehlbcdedcggekalbdaflbebcdlljgbkgjelgmfmeifdejmiggjcclbbkjiicdlffmchjbmafcikckdeaghbkbeagmijamhgjmlmmjbikdkkfacaichgccjhihdfahiifkifbbfgdjjgcgmiaeidfehadljcbgakcjcihhbdkeggbkkhmcgedmfmfmbedldjliffgbcgeddldjfmhmhilhjfmibjhejhhgdiidgmgmjhhcgglkcfbecglagaglfccdjlgahdmlijgimgaejkkalhjjbihimiffhdggecklgjbleilfljbghmcdejhjlkkajkimiblgcegeiliibdhllkihacfkmdbjhgfdbhhahmdmkjhhhdddiifbjgffhhddmeijjjfahebmhldjeefgjlckbamfhckmbidmhldlklgalblcjillkdjdgcmhlaimklcjleiaijikaaelhhgcjikmcgkgmkebkllklkdajcdlbbmdlfiaamceabdlhmiheiggechmacemkbaaalcfgeccaddlibccdfgkgkifjhiehmdmkbajelmafhgjldbdamalilbaemjbfcmdgdkgegcfcajbbdfamfkakmacfifecmbjjlflhkcibdagbhjbjagigjbekeijhcfhajmfcjdcbjibckdacdimchbjghbmhehljjbbaafafedfillaeiliedgclkfakcgemcdbhmcllamlmeafaaicahiamggaijfhldjhedieccjeilkfhmhjbhefbmlkbbdhhfmikghkhbekfjigikbbfgjagglmhbjchdfllidkhbhgbfbcfmdemhchhbbcidcblkbjklaedkkbfhibfjfcdakbaedeeljimebbjikejbjilcalgddgjjgdfebgbgbfgjdmmjggjdfddkjdlfdkkhgmjikhhadjckabdkehbdbflgiibhaldhlmmkdkmjiciejcjldacdhcjeijjefldgliccggjcbfdamgakkidedchhdhghmhbhflhhmgmgfemheechehljkhclilgjbebljhbkmllebaijkkjhjgjikmbbcjigbjdglfiebdfacaalgmahmbcdeiigmddcjgibbjaegafjgmidbhghlemjalgkchfafeefcbjbllmjkhcjlgmchfkidkhkdembajjmhdkmkbickcbcddhjaebdcjlbilglcbhfcgldimbjhbejhaeikmklgehmebkmlaeijjbibihegkdgjecjabljgajjmhckddcmmcfcdgmgbfaajgjlimbjfmikdbcglbkhfabekgdbllhljgmejiledmbemdjiakhdbbgcjkjjklfkedgblhadjmlkdmlibladfeihflhdjbdaaaagljkdkgmfhcgmejimicmfdlaiejbebheghcgcdfaelflbegdgedjicbkbdgdmcllekkdajcmmlccchclhdcdbgbgcfalcdghlbmedmkleagemikhdjckelgmijfimfkbdajjlfkmeaddmchhfleejekgfllihkhmgbhihidflkmfaimgmhaclikckggemlikhekflgcleldkbgkbkfeemddikimgefjedgemielihkhajekdaiacihcbkbhicfcchjhaigafbmddjdfimafmbhhhkiglbklgjceibdgibfjcdacgmhfbdffhcikikekdmcmeehabceejlhjmfchfcamidkamldbemkjefdibabccckliemljiliagcmjbeefmbkgmggjkchckkgejjkmamkckdaahjhjhbkgbcfmlgakbdgakjdiahgjlbfkadfaljmmhiackhcgijhalfeclmkbbelijhbblclkkdekbcjcjlhfeckbjibjacbcmhlijgkdikeimahhcchfegaclaihhkhaemcjkjkchldddejflkfmggicamkefibalabccacgdgfjekgehahabihhhhjfbfidkdjkceljaikfilckgmbdbcadigijbdbdmdmbecacfjakfcgccjjahlffcgkhglgklmdlmgaeifcmdebmmgiamlkbaekibidjeicjelbibfcaeiijbgcmmmgdeadkfbdcjceicdliaifachhfibjbfleaeakceehjkmcaldgdjigfmhmlmiefiljbllaimdcaeidbflkbfgaeembiecgkedkkdlhajmafdfjmhgldjakfkjkbkeggjijkfelmffdbggdjhcdbiaedemhfijefdejcjldjgmmllgakmaadbiahfjabgkleblmaciifihhedaclmhfmbmmchldgiebleeehfjfllgaeecggkgfkafeaigbljjaljdachmbakegdeaijlbggbgmbeeiehcmmajkbbkdaihagcfabamggdbiljifcabkddcfkgmlglgififildgmcdekcljjbfbakcglgieiilfjkhhkjgcafcaebmiglfgiehbhacfekiidibkklkkbhjblicjkmeaafimdklihfgigiaigkkfggekljhckgibddkeiblmemdfdccmcfcfldkgcmhealjjfehiaefilfbeamlbikdjgldiaiededalhjbkjjalhdaagaemaijfghahcgjgakcgeklcibfghdkejaallhmcbfcddfdaicliakgbbdillfabdgmddicfahgfkmbelcjeackibhhelaljcmgbijdbjjmbiekgbfhaghmdijgbghmhjdmhmabhfimchmfafjiijaiijgffgmeacebeldjkbghfefmgekiljlbfgfbjcfagbhhglekcfjjbidjmimfejbgmeafaffghhbcacakckcjkaciedhkieakghiibhjhlghgilfihcfkdagjcbeilemimlglibdajcekiijacadmmfbgbbkfclihkmbdgmbilhebmdakhcgiihedfdkjfidcmkicagmcdjifimfadcgeaklfimljfmifgkdkehelljbmjaljkfamdkkllgeacdhcjambcilmejmcgcbdkfebflbkmgemjlmalklklmimiembkfbjggigfcehijdilcbfkfmcmcicahjmmafkmfmjgdmdmddfkjgmicccbfeilbhglbamjmljajihhiciiemiihfcjbemjbjdmfhjjkldkkjlimidhilhajibjdchgjllfkhlmicglfbiegjmjjclkljmdgfmfcmajmfmcbiaeadehbahbgamjddhcmdklclcijcjfkiahjlhicmieehdlibkijkcddhagihcafkhgdelhbfgchhjjffhhecgkabifibjfkkfcbhjflmmmlagmafleacmdeaecjehgbfckiilkkhflaibamljabmdakfccacdgfegmjcllgdcmmmgffmabmfblhecblcbgeeeffjlkcmkjgdjfaeglckbidgjegmicmimbejaebbimaaggfcklllfdajfmjhdjdmlakfkheebkkkiihhfmhcclclhalcfiimmfedecekddfjmieficflabmbdhcbjedldeggccakhamchabkcmdhfhajjdafhhljfbifedhfjdjmllmklhiihkghfelhbjigdiiikjmhgjbiigjfeijfdbdbdbjkdaeebailcebfbblmiglchhbfmmcmehfeigkciclldchmejhhbljmbccdlclaifgmdficgehbieiiddceddbhadbfflkfeehmfiklgfcdhbkeaccdfikekimclklkdekglhbbcmbfaamaggcbefdciclahegciagdkgkggmjlbglaeckfegjfcjddefeekjalbhdcibihfbclkafefiabdidclkghdkmdmaembkdfdjcifjmcdcdimbkjcdlglfbmailbcggaegacefmaaalbebhfehebbfjjjkagjhladhmgebfelljddmgmdcbajdahdfgilbkbkjahgclbehbjegigmjlkdchdgafkjgbfebfbmeidhiafemhjilakmibgekdchlgbfckfmbcafkhjhbfjbbhmbmdahjadmckcbkimgjmablmkgggahbblfmclcjidembikgidifcbbgabbelfidedefidamcilgejakidebdmbakjdlfjmikgablhhimchegaeegahejdddafdilgfaflmhcikgiehibcbmfidgaklmedhhalfdhegbadfejedidimlaccckjjebcedmigdakcchlbhecfkgaibheflecakidlbldgifhigjhdebgigkhibkcifkeaajfamfallealgmkejmkikbdddgljgmfbbfjgadidmfgdgjbgmgkkidlgccbjbdjblemgkagdlalehfigkdkdeagdjccmejlcjelakmmijeihhcjabghkbdhlcfllhhcgfdjccffmeggbhgkhhikjiaamdilfkahhhmdeihlhaaelcfggcgdgiflglibbeablaihechdkbhfcelcmmffakfgkmghgbgfcclfkcbdacejjbgleicidieiihakklbdkjdbafkdghelcjbglkkfhjdglkmgahdheccgkclfgaaakekddleellhkdbhkfelmficljfmjibdlljihajebkfgjhjeedilceadicmdcdijllaeggdjdfldcjgajgafcflhdagdkikbedkfcjafcclhdjemcaabbijhlahhghkjhdjhkckmkckihebcjakkacblhkjkblccjghlceammbefdggafgkmcagmcjiheambjbhbkmbamgelheelbblalmcimfgbbjiahcecagfkjfdiecahlfkjgddefegibbmelhmiklaielakdfiefkehbhagjladhdelfhdcdmekfdjgjkjjdcmgbjhcdbbelldkllifdjgmljbcjgdicldkeikkbmchbljblkllmalaadeeijkekbjcjljjfhhhdmgabhajafclmeecakkfhjdmjbhfmkegkldfhmfbfclfjjjjhgkgcbmefglcdafmacjjmdildhemjheimbclfjeldlmhfhlajlamhjabekkkbieihafeebllgfdhjlbjddelccmhfimcmhjefablgggljdceiccikkdhfckcmbihbccljhlcgkhjjgafjcllkhjblaidcfadkfggiaejcgbljmaillkcgjjggkgdkcjmbdaegbhgiiilemgciegjbaagcjkfhmikhkabielhfafhbkdddadjigdclhlmjjgmfhmmckjklhhibkmcddjgfciecbgdbikimmflmkfgadembghlbfljcgadbkliaehmjfibjbmabmjdfbjcadmjdalkakgcckgiefhjichgahljglfmeebbjacgajhekleigfdckgkemkakledllkkibammicbjbmfkkhachgjjfbmhaiaecgmlmkhmkafimccblgkkheihccbachcimjmkelcmdbcacbkgclgjeeffbfckehclmmddamlfklaafeggeelkfakjfealblflfafbeamfgjadamlebdmlmbdiigagalmalgfmfigeakafadmbjehemkjmeddelfbbhmdeifakhgkcgfhcefaaicikdhgjibhfggmfcdfehaflkbagbllmbemmalidmlgalcbjfdlahibaaaafklbaeeljalkdhkdbgmkebbgadlfacmhdgjikalfldbijliebdmajjgemahjhcggkehcikajeadcjafbhhbmcldmkjlicbbjahlmhmbmjjjeadjiflgbgagiiggjdekafbifkihljffjdgjbejjcjhkikmhecggcmecilemhkmmammeegijfmhcbidkbhimlilimllcmihajjbljldkhacijdlihejdbfkffmekcehcjcfbaeeiiddkeelfimmeimfbaahegjhjfhfegdhmkfmmihjilgfggkkdmfckkhkhmlajahjhlamgjbbdbikcdmjdkmlgeidfgeaadlfcdeelmhbimaeifafleeljjgageicjcfdgiegdjjfikgacgchlgigfekedjalilhbejeahmllcfidibkijljkikaaciljgjblmadjlgeahgdjadmbjjmmalhhcmgdbbejlhcabbhkdidegmiakkmgafdikabgkcdlghjdfialdgdmfkbmljegddbakmamgaakagfhllddlgbjfkeadkdbegefejaekdmadilgicglldiijljiedfblbkcmljfdjebedeeefiajkfmgbmgimiaicmkfkajljdeahbagmkjgddlmemahmhmegklmjaigldajejkgeemfefmmihgbfbikaadlfcjgbedahaicahdmagckdkbadcihmjcjedjfbjkhelcehimfkmgdifkigidgihkcemdfmcbdejbabhjkghhfejlbgmjkbimfdfehghemilabgalalceeigiemaeebglcfbkhagdkhjlmdmkfekcccbagjkeikgjjmlcdgmffbgahmlgjikfdijgkjmeicfahmmaejciaadbdaddjiflhcgjbdljkklbfblbgcgjdggfeefjmgadckiblbdilddhlgmclkeljmfmlffghldjieemdjfdimfjggdbkckediefkhjjddhllambjaijjceilbijcmmaealhdajedmdddkljchkhmeeflialfbmmbklkkmemekfklemfgebhdmelbikegmhhdadfkeammgfgjbahdbiaimgldgmkedifdjdjfekilgkbfdmjadllceamkgmhhmbgkffbkdbchbmcmckhkaeeagaeealehgiejalclelageffggemkklecbecfglldhglmcmbhahhedgadlmhmigfmacbkmljldajembjejacjkfdebihlllalbdhclgifdechfckkgmdfhafbcihmeklihhkacciaedchmlcikdhlbjkkiljlgbklddlfljckcdgedfbmjjfcamchkcgfmackceefeaaimeaglehfidihflclbihdlleegkdedblefiajafdajiaggmibdbfgejiiiimmcllkmabchamgccfmmfdaccikmeagafgfkadchlfaacdcllhmcmckijchmidjcllejdabkllacaicaggjjjimlldgihbahabdbjmaibidljagcmmkfccicddlglimhfblihdmmjfgedljlfmeeajagmfmhdlfcfefcabkdmbmghaamjggmhijeihbdjdlhhjkjdjlggecfkeiicikcdgcfclmbajcjbcjifbmbfjmabbgmccldcikelcdibekkghedhikbfdbaejhdlhkhfafbbbgjiaegladbljlkcdbgbedflimgfaekaieaijcdjdelcdbhfaibidieffekkelghgbhlldifmfgccacamadgcibidldegibaceikhejckaaijhalcebmjhadjemhbmfkallkbjfahcemdlmjjaiilkcmdhhakliiekdeifhmageflaellmjjbafecijalgdickfdjhmeeklmfeegiffcalcedldlaeillhbmmcamdbcmjhlfakaaflggkamkimeefmehfcefkhgemllhbkmmljjhbaacacgkdhikicfagmdhmjabjahdimbjbcemfidcicbckkbdlfgicmihgjmaigigedcmgemfkcimlihighfcifbkmdmbcieffmmbdkhfldidadadfalidgikaffgeajbdeeibggiamcfamlgmhfmcjhkgifmibadghcabkajakjlmcbdkdkgdfmmelfcmcajdmlekhgkieceidgkhbeeidgjgfjccldkmgifecbddfgkklhkdkmgbgfhgafddmadhlabmajieamihljdiajejilmfhkeikjhgfklgijleegkldbfkcigjkaihmgiafhjcgijgkchfifmeklfjejbgckhmdffdiaggfibgkfddelhhibjaifefkgddfljdgbmiahbmiebkhdifhhckigmembiclhlgamfejlcbgbmfgabbkflkegcbaeaelcajefacjbffblkgblibllbgaeeammfblacdhdchggddcedfmgmighgjljbhajjgeiaecfkbejjgmfbjmajildamdhlghmccdhakmaffaeibgbmmimajajgbgeddebgjhfkeldbhackackmcgjjlafajecdhjkalljegcmciidjjeckkflmlamadkieimmeeacldchhamemhdjmhehkhjehgefklfljdidfegifffljecfcdkkcbadccjmdfjijhimbgbbjkiaeagklebjekjeegejlelaibijjijghdlhmkjjaekjhmfchbkdijbcjbjimldbgcdgkegjajialhhifcjidfdikhmjlcdbgdlljibhachhjlmefjblhmbcjkjcalhkhjbhgjjgbdkgdikbebaeikdlbmbalbkiaaagfgkfbhjcgmflgbjibefbfkldakhlidckkbjeebefadgeiegklmmbmaagagedlfbckjcghmlkjmhhjeibegabkajgkhjmebkeiikkkieebmcmlggjghbiecdbfakbcbjfejjlhfbmdljhcifcblmlfddmlgcfhlcbehbcddjkcckkcfhiaemilmcbcjdgdkcbmmgbbfkgjbcbkkamlfabijfbblgdicljfefkdejcgdjcdgmbbhbdlemgbkmhgmdjmihekgkamamacfkdkcfjbflmdmhmkhecblikhabkklkfmkfajefkjdkkgbfflegddbhaddjjggecifffbaaijkhlcjblkaeefcdjdkfjjlkecfebfbjdhdheccehkhamjiiddgcgfelhaafmhfdieeagdhibfeihlefighebcfkigacmdkmcjmgdlhigjdmlhmhaeaffffgleeejfddbkgeaigaahbhaefaaijfkmihcikichcahlmbhjglkajdkmdcjeafebaiabebfamkiadfbdjjkihhbcffmbikbkdcbakkmldhmlhadhaamedbklefkafjcmjficclhkiecdbicfadcbmgbdegebmdbffiigbkcdlbdlgclegjlcdefbakccjgdkhdmcfhlkhkcbbhhdhmajdhadjkcmgcgkdclihdkebcjekbbibfhhgdalgmdkbblmelgadkmfcbcelccbimmbgejidhjkmkjaldfbfgigbffffkllfkbmfbflckjdkdaiifdmiceajekjkiefheblkkcahkbmkjkhhdbfdfbhjgbilgedkhiadiifjbigmajgjclecjakcgeccflmfalelljclagjhmdbefglbahggbhgfcldmimjacamfebickljddkligficidcccgjfakilmahm".to_owned(), 5, 3, 19), 13);
    }
}