permutationInString.cpp

// Source : https://leetcode.com/problems/permutation-in-string/
// Author : https://github.com/xinsheng
// Date   : 2021-11-30

/*
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
 */

#include <string.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

/*
Idea:
Because of it's permutation compare, so it's impossible to compare as string.
Using sliding window method for compare frequence of char can help.
 */

class Solution {
public:

    bool checkInclusion(string s1, string s2) {
        int s1Size = s1.size();
        int s2Size = s2.size();

        if (s1Size > s2Size) return false;

        vector<int> freqS1(26, 0);
        vector<int> freqS2(26, 0);

        for (int i = 0; i < s1Size; i++) {
            freqS1[s1[i] - 'a']++;
            freqS2[s2[i] - 'a']++;
        }
        if (freqS1 == freqS2) return true;

        for (int i = s1Size; i < s2Size; i++) {
            freqS2[s2[i-s1Size] - 'a']--;
            freqS2[s2[i] - 'a']++;
            if (freqS1 == freqS2) {
                return true;
            }
        }
        return false;
    }    
};

/*
	Solution s;
	string s1 = "lrxdxvfejdkrnjillizofhtcsnsaayremyicmvfsfuxvmlskswyfjwxdnotttdfisbfnoldsfaarpaesaltnvgrdoktdnxwgyblyshlhlubpeamxfrsfhtlcezzwsjtvcmzkpvfvmhphwksghfnzhbwogziokkkhgvrmndwsjjsegkdfobnecberwraetxwdxemzpoakgnovqpjgslmakuceqdorytxawxndpbkvsbalgfkreaplyrkbxwzfdlzsmoazxcmrmattzszqehtevafgiurhjbtfmztjgozkunklacupomjjafbzjerxlvgmnsjqcrsrbrcugaofbiuvibjmekhyddhwberuoaxfghtdgjwbjlziraohnmkhutuyftiptmdeshtyhrhtdkhgkzoxnulfqboeimlepwyihauwjsermzmefzlkubovxhrtkbfhopvhwuukkacivimrnjaxmpecncgxfelmcfgnqueelqssgpxpidtswwrrlusgwznwvuvdahajoxflexnctsgmjchtgfwlqsfyoamaaaowxttgshiszohczagbgpoqibghhawdjftrrgpuailqfpwzvytgwdyqfymihyuwhxzhawpoxafxvnwvkhwubjypxjnqjkfblpeoxewtjfnlgiwfkxuirhpbeyokyrbnmichszrsntbaxrdiznwfiokbuhkwvmhtunabqninaztpcvzptfjnhtxzjuupwvtsaateiuerftqjxqkljxkdindkrnsmuhouhpquabwanjeoyaheqgdkdyqsqdzlrdwyrakfdphasupvuhwvtsesrlubcapcdzutmiyyudpognnmmncgphgmfdozclwgvxhhsbxaexuenknayihkarjrbipmnujdfqfvvfbaickybuacyuutbarjsmveivscoktcpfzwlcjemengveudvdlcdjnpbjbimokldsbjlsdasbgjukkoeucwlhtmkxhbrnczapqhoyhrqaogbkeqsczwlloqiguclumiggrijlymcszkqnmgtzjcblnylpigzbwiynnwojnkyxnmgoodljmmqcprzznsmcruifltbdujttnpjnttlbfwlclgewsdcjgbtuzwsayatuqvmebtvihljkaewfnqbotnmkabcqsxbohqleqlrujvughzcurfuhmhfklbwbaudmyfttsikiwzbvlfwmetgsnxxlmjofrtfdfcsnqbyeecgzelovranroxccdaqyfqtkjxeqehjoeqytkaombdgfajafmvmqzzxfaiezovbzcyihaucpeopptarcwihwklrpvtkqnbbquqnlmdwygbtkstzwdznbevlyfivqflpacmtcsarbbkmenyijnjvwlixhmqrqrejwznxzdiqzrrfejxfmcdzmfkjvbwfmstilkrmvviywuquenujtcqbhkyxbnbbdoxgyjpxfucdmsecnzstjlsivelupyptdogsjepgjtwgoexaxjfduvkldfudwlxmnjyynypvdvgecyhflaiyrhbqmixmwgsehsfmxyjzvkioaexjbcnakbakbrvtwgghwhfsffnamcgphuqqxqvbdmfhrzxlgiunazqhfsxgxxwktpjicnmeaxyhyfauegcdiykhuouqqnybgxcazckmzriyzuulqeqtgjuawvissukncpataietvuwirkaifroelxsptnolduugufycgnvamsardwrueajvhqkkxkkhzphbuqbldukjdqcznwscvnnqnwxszplqyfuctorjcbucxgfctibwfxftrdliugohjgmbxqduvwgrdmmawyhfgkkbeojyxkoftuluolffjvygyzftmcuthegrxdkyegkucgnukwvyjqjeewteaivfoybrwaceyasgwxsznkjzwyfjoiqeclwlrnyqdxmzadkjvhjaeghfcaiyrjefpkyhslkeogzgijtdymtwcopbvhzcqficucdfzhndzddunzhnkmllhjrrjcvksisdphhmqcnsrlmyygxhlakemvncrogiljrtfyvdrujjwowwjxbjxpjhebvheexkniipvotlumxpjplncxsrezcxmyansqmarfwwtwngvcgqcijzrhvlwalkcdsrccschgudpahdvlunyzbrdfevmnoewvavrklwvfiilgtmtexwzfmgacugaalcxqeplsmpkplutliqairwtbytsxzlupqplbpadgsiuazxvrdwjzxpijvwytgmsocughjqwbsvozcfbflqgokqjdxrivnioxcgefxmkjajkwllqdcepegzzylflfqxclhsooylinxpalctbxsvbdjqmmcyqfgfytstbpmjgmqhmnnesgovyzwsatnvqallzdjrtetzdxhckykznmnuexzsfyncndzbqstxwppzjolipszefzxqoyjteoykmrympogufseghdqlvvipuwfzheescacwrbxkaqcutfrngmzmqxeeorppkjgdroxoqdkyaawrpcjtfxzlfgkrguphggygibcialnnkvlnevkbapazmpcguhmjcmizjsinmqjknavhumrdmjnbscndtfapztvczvhkpcowavszavfcwwlzdddpuliglnjucqziltqwlsibodwdcbmorwyyqcvwoesjibeqcgsbtcelowxtzryhvepjcqnpmigbdbuplezwgcqekhxzvsbwlaunotrhhmdrrfjoeyzwzygeypgpxonkzriqjsecoqdmeslcfgnzlwstigfxogzwrjznvgtrzjdvdiaofktlzpvnjftauzfmgigxuydyddabcucklupsjycdbdzdghkiryjrjuretnulfczhhwdoayrrvljbihhbmxvzyjxrwkpmxxephocpleznusehkxjgjqlalbgenuahcqzcbvnurwvtwvrvefnkdwywtokrxhstwwybamnixtlokktydnuqrnxylazddpvdbfhtevujagbvqkbjtcvedzrqpkwmxnsugrklcimmgbjmnatgmyyuvnbuffgjcvclkglhdwufxclndhyvoecrfqfxtmunjqavkrhyhlltnxwjsdzvkmxayxmgvsoaewlergrdaxssqtavrkazjkamfeyvttdytukwsqxrevtfquuanjywitzajgdlsgonmxjwxqiekadyohkzlowywqrmnydclodaichygaxhljvvlnbdpsweicfyntnxmaxotdnizxdfkhtnegosqynavfeludbsxylfpsxrnasizvozwlljokgirgewaskykpclgictznfysqmwpkyjntcvikxapgxupqewswsuqcnlajdndiujuwcfjkhysjltdbjjgxgnbovwzrcibzwasjoitdrpyureacgvdupxpzqepymwjxruyxkjhlsgiddghluhkomqmpzbucxryifzszpmknuakmbmieksazgsmzpuybfdlpqlilcqfewgqkywbianhzgizbgkruslhepkllojtoewgrhxmqlziexxfacuzjgvpgbusktkkctzyznwycsklkrrjrvbmxbhrhpwaketgqdubkavullzlhxdahukoajvrjfdmcltylxjllnwycvbcddpxidjzhkpwvlbrnxmnvseioujesuieatdxcptqprwaukeqdodaedzbwmybatapayautrbyayjxtnvcniqleohffgxgsogwslduzbpkaxtxwzstjftgriebrlthrhplhpqtglcjzoospsolqtofgjttxzpdceficxvxvzkfbptevvmjiviglepvhatglwgbeywcsgrqrttwjblyskptgwkhlyudcxolbkajzjeuvdbdourryxldpzlbfombingjbamxelfvqnusymtussovzxkyemigegqlqoprynkwuwhxmvkacwplrgsdxbcoykxbgfyfuclxcaxpzqgukwkbvrcmzvuzinucgryrnjvgysihixhcknpfgjmagmlpihnnbniksegyxybmgwsqgitctffwgudyvrkhnnuqczybxadjfzbakmrpzqgsfdtupbrhkyqumimuwwtwaugrpwppfcgpxkumziermyqqrihufxtfklmjsipuyimbrfatepkufdonqditpcnxbanfxfhmmwutomluagakhinnrnjwamaztgozkpwyxipxlellbszvgewelbwvkxxvrmtvuiivdgdfpwwuwvmxnewqkpoocwbzmpbscymmrbrtaazhpxvktdoukayngafglbvnmvstahrlsxwumubkeceevztlzwiyfiwtyuiyjbghofotfqpygwvgzlzieajohxtnfwfjtpezunhtezmgoijeullayhjlrklddeiujhukyhgvwhztrvrdcbxhuvgiwmjwetjmwzoipopdegynbwjbxblgkgcbeljnlmdogjlmfcebkpsdnojqxzgmmwprbvjnvghxqbozfmbfpohiwtmdzumxlgtspaodgmqrykogolwgvklwvcxuwqztapgggossaayeiyramtvoicssnfouddszofopvrmkhyihbiuabdzrxflubidzkorufphwqryyznzlcgffamyeacfjvdkoilbvurswxuwbfsgjqhsajbsbvzxwlsazxgfmnlilenuuowslmlrrbzpkmoelvhpvqdwuutwdsowwldmuwzvouqbynybgnvojeyzvpsyzyrmreeahzutgbgoinadnfnctsezjixjdqkrleovfjydtnndeuycghsuwioyqjpdwhqtgrazzbxfwgykjbvewxrrcdykuomrlhamlhxzstykmfncbbkozncogbthvdrttafboicppqgfuvutfsrdvpnvavatvpfcpoczukoyskqyinzhpdunoxffvjpfxyxnelalhnwmzjzcjbndqkutxlekciqzxsgdynwvfuhkqlssuywktmsgbrazfedmjwfjuoxroanbipuiilqpwzdcbalwdxxrpdkwdrjzxlczzbwxlecntxgstkhctsdjocleuhmstcqnvlgkedyibdcdohnzxavsdbjvxucnuirrjenhxxtsyunbydyllkijehpwffykdjygganbiypiogebqmsndzdkqyodabqrwitrmhwkaptgrtfyxfjtdvyhbjybfftugtdocvomcsfowxbdhncpogbyioijutjgxirsauzvlvjktllxucqyniowzappgxvngghdpdlyrzvfzonmmijwxxbgvaikrswfefrruptiabegaomcjjnkfoazlyvdvppywcxjpjbxauyejrfixnkxflguuqwbuxocawwuhvhlvrjcklekcwocblavcitgpwmuxawxrvgiibgozmuyzvyonyvgyxlezcajxchiytjoaheozixofdgstnijliogyvfrlmaepvifdrqfrdufbuhqjqiehnakvcqoxaskpbrrgynnkqvnzhkbglpaeqdvqxxghuixoydcwupbvpkelrzfwlzenzoqbulgvvkowpddxcpfrigxgeuccqvkzkfplcyyaqsheqjwosqsevbuvpglnlhtoieubioskacdfpvorogamnbwnajomrdfrzgkufouftmdiowtxkmbktzvvnegotgnzmklvnhmwrmajxytpexwymfxcerimsyzxhraehnhmshkwmcvaufbsycfcdjacgawmvwvmvybwqajhflxmbjenkeyvyullqyxotwkrtdgglgrlxcjiicnsutkjldirboqlmvfrlllxtiquhfpxhczzrmumznjpwcfmwmemltqvkhskbchpwhqruvqnqixbtorkrhxomtuybgudzonchsslxyslgzecpdavfxescyoitwqxnvcsepeonbuzoyoeypezouczbzzbnmzccgkhmwfbmeicmwqjdegmbbckgioqwzapatrbeedksjspndjlvljlqqnesduhbbtmgrzpbjhorzhknjpkrxznthoxsxxrnppmalnehvkkpdoskffkqithkqjgmtbxgalntgispxkgqvhxcydzfsdkuwdzytkolzmywtsqqbkssplynomcsnfethndaicofgxsaslupmgtblvwvhsamejhvdqhuijdwglfjpfagvtjmmghikfnetdewtwqgsjwtlvwjcifwurvaqwbcrpiqghnntivzzqdvuqtucbwustfdgpqvvneouriwiqxsyrultkiysyqcgijkiqjrxnfwrxahlkrcnodyjtfybfspqckojtriwfojgpcetjayrgjtrzigvtzosmohlywfyrbtryxhlcbhadacpplueillitgruqhexwcvhxpphbtksuirsnjnxvxyyiibloqmrevjlkghynenizwpkzduifnlfksipmljdujwqafywlvagomisejmbrzbxnogrdkikdvdgfwvxdoxxahtskkyonwlaulsrdjzokijupfxwdsqbveyieuwrohupopshocaeqdnsphawwnvrzkyzazdccnyodxpnuvjshmkrtmcklnqyeoovlexwksutsvhkbrhjhhodjidvkejkkxtvqtcpiiooltimziokpzajzfvpylcoxyglbkrglvnzftsmzmxbovviavuxezpxezuxzzfrefvbukfuwzhxzjkfaynfcjvkvbndrdjqdhnsrcxicxsxfjsdpvsmwvpqijeemnknsofeqywovbdpdopggrfubumvranfzpmehzuqgykddajkwqllyhalnyoylkyoczxozzrebnwljnbxvdxnaprgqwmfjeoyozqwqlwudlxjpuukrqupzigbvmoysjzpprcsusrzomywxqfpqomtztgrfggyhbbceiniofjaghnlucvtfdupgbhbvnfvtgexgnvjvwdtyxxgxxvgymtfigraqskxvnehqohwzqzkhxpifqrutlytfverrlbdwfqkiejvatuzccuxtousmxzppnkngxanzjhugytabydqynmnocqlcdxndwohtptktjdrxgtkvqyzoimgmsomqtnebsdvvrdhcalhgsuoglebfdhafgezwjnmgoshzoqffbtpilpberqitxkzyglpdkcwwvpdqjzwcvqiazhrurnesjrzmvwvdboouqyfhyeziceekrhncfjhdeumvxywinudsfovinwxsbconemtexvfafxhaerjvqnkchnsmgljwdddjsgcadvavlbnikfwvdsckvluigdvcfuezfxxxkrylxsnhwuduhfkdakllkawxmyqbkbzcqjmsbgzfpojtlpqvgtqlmwurarmavmmiatpfxvfzfqacptkhjgobtcsnazpbroehpizwtpmrclahjkkzcmmjznsyaglerbnkzetxrojtsqffhzliqwzdwefypaotvgeiawuwxxfkwlbzrntcaloqbubnyjdnsspmmlckzdpllmcncvrkdqrtmfbbbjsmuamsiipsqzexrckpcpnfnhjukamxctwsbfrcuuccbankpotvedkkyrmbttbzasydxkszzdadjlzrdmzbqtsqazuxeloeutjxdsciiugbwvfvwykptjbmrlxkqxaytyzubavioljyymsmkdzbiboaosucwfvwovzwcblglzdwuiffzclexudskropugxsszdttwruooehksqtgwabwrqxmiqcidjpadjbyldjmgfghezqzkqolfueavyousvfmyuwaaluszwzkgalilmguoiecvhsawptpskudkmvbniybaslympseyyinueidogmoiedkqvuoywnduxctjjvjhcphtaddsasmzrxwvfxkaypozvnhfalmcwvqcaeszthvbqzmdohdeqkfdeeislkblohlxrxqydoogzevgsbzhgrvyxvpgyngsgqzodgrrtqsbnpvfhybjgtuufmmmsekzmuyuejpjtuisqkrptauhsjcllecpfyttiapogqylltbjhzrjldccfybxsionmqpqeyusrtastfoqksshmziezadeogrojwcanijxknuvruioetfexnzfejkkxlxrktswgqdgkeznvyzwkjlixlxxprkbtskpjezoycykjtxjorxiydrgvftxttaciifiifbdmbhozmuftpvekolyxcwnzhwgmzcsiumegewfvyxwaijlgwnjpxohsfkuxxfytbvrkcjzlnxmmcgjmpjzbovcppppmpuvfcknlkyhbcaevgviusffgceekjwhswxhupfrtxhwhjmdtiicppzkcplcqaifzjzfnbbtistgucduxqprfughepxnkzengymokugzokudxesaoflosfcxdulhdqlhebhmuogzkqqmvpsrnljwszawaazgofirmswuogqzdbezgfhydcgtcmbipuuvrzzrlvsuxqgesprlrmdtvzukkyksflpojpmfkurnmjslxvkrqbknmmeavkiqowseqiionjffctbfgvdlgridoowjwflmdjdjpziiioguaspnacxlwlyosixpbxukglrnkzjtcalatqfxqrdrbfqltsgonoyzxaittzathzvrtjpmbnbnbuqmxfcwtxvnafhiksmbjxpxfshqkytwunhflybohwzuvvpwaqlwdbxnnzdnpikwnaxjyldyltfoiyqvhzrysfblphtjyaizftfmgbbicjfvbbnzjjofpymyrfmihrssgxontbmugivvupgczbajxodcdfutzydnfzwogncjrnopjsxkxzpxehitpeduciiiwiowxlbcdjfekjpzhdlmtkckhldpwcqntqnoftmjphqcfpydbmkpgwjpnjcgwwshltewdooxmzmmhwpjckxbrcwismkmkgnduvnbnjntvaaasxocisoreldzcpmnftluzqrvxpftrrvabdojqqklqvssptacdcnlejxgjyvreamirjwvlbdvyuuolbcdgoihylhkpqcuokyyfzzgldesantmyoqgcbyrkdzhhteybvgbeeektccdgkvmmywzdtaspyuilnmziledlzxuhpmcckyxiibjdaxgqmxybpewnynlwykabudmtmjwoujqstusxfkpnbhgjqoxxhxcahezybokuanmqfbotwkagqqohaxytqmeruwakokwomfnrdefuljckiixahakaxsdyojvutmdmgxdiegvlblyhogqlewcddesebpzleihfcrttmkewoalaxathwluyvvfbavhjsqkttzodstcekbpnthsvprfijukbuvtlqedjamwfahjhvivcoarduvrhczuxjbfxzitlorrntwebjauxejwpswfksxbtecdmwvtvjgvelliisqtmbfazilmmizkbqiifokdaajotapnpkqhdgsmxhtndlupujojefwkasgsqgbqnhkrxbfunnzkfdtnlisryccnoobvewvavmhwejomytxxoclwutmthshxdddpokdprsfumpcmqhbtwlmdepchvsfkoyfzlsxnrmmuxlktunydlndafnvwhkymapyfwwgkljzufstoofyguubmmhgqplgyudbpopzvsijjerphhgyqqubnkgqlqhaiyaulzufdrarxaruxhbzeowebppjirmrnffrwcmpxgpeonfndbeivayxqttgjqqpizyuiupftoyvaxxxqqxdnffhmfmtcfkocawihcyopiaxvjibugwitexixqxsuxyubcdysmgzelhgykjfizyuvqmiajlokobiwmnuggqaspymnwfvorlpzjikffuctkjlpsrbbnzpjqgxxbjfuuqkkvscynswjnmfrcfwwjeqntczherfhjrvgbpiqfkhsgjirldsypktnjphrdiuaiiuimptnqofmiqqlqvnhwiitgexcjopbshfubrlsdbvcdfdtoufxiphxrilhemygjytnzvabaqjwbckzbcpltovszpffbzvhlbatguhjufkjd";
	string s2 = "ylcotuazxfmsojotjtnjnbmiestmchaxbgxkimkcgtcutoqfunbgnastygeqvljyjnzwssxenqcqmlsfsxyznxqauakdjcczivtdvzhyfyzzzolhqfkaaazkjznxzdwicdrhlbxnwahwichaymehyqtwimnxpszgpdpakeuyqudenyntlpogkitjklxqsalvcdsptrhgdpmuknnnszmbbcroqbasxngigfnuvaehxbfqpmvkmmdlofgemxhordbctbafsvwutdnzmemmvviwubpgjsugexoevbbshdhguvhhvdkstmwbhtygfpzsjuqnxzamcunrqpmceteowiuqrstiqwisnfrwjhlbplwhlazvkobcbzgtaszyejkpcwnpstvsydjfrastxtxgsaeotdgrljmjtcykqvmcwoqjyrsuduekjpmijyotoypocpadvlzlxrpqojoboyflqecaqqkbkuugezkvvcvkuapxiiommosbwnrzxkesrsmzolwbtkrejjmidkbjlleqjlbwszdujsvryswyjmyetbmevrnnmosbbrdjnrfpjunbujpyvykqvwylstblxsqgxfaiiaxlkpkqypseezubvniivhpuzifpdylyrsvskexspzrjppzhkzkhnthtiwtwpknlyyqkclkplsdxtlxcmaplljxyidzwtykvtopfqbckueypiirrugnpvzraezxxmbexalqptvqdyqehyfnvdxmfazxkqzhgqkjdwqqmykvyhfaojgltqwrsesothqrrpdgmepgxtwkgwkxzzdkagvvqqhcsgxeqkajpakymxhybbxvfybgydshwneensnehanrrpkqkmxnyizlficycvywfdvynbxbxkleuhzqjslbolebykvqiarifxbofieboyollxqukpslzlorwcdadmbalgiiyarhkbevhsydredoafxtbkbgghrqrzlwyxpyxsesqobqgvdrjnrtefywdscecurexmqcvjhbeareyrzskicpzxslhdsdilsvdzejjnzuasswomocgmpvxoyolkbvsyvrkpfgdoljgaxzmjrzbsdqqferxhntuklenqcofnrcisedichncejxujhkqbluvckvogiprrmmqmjivomhhduyhastanololwdholknufuipjgadcbkyfhhwmlspckizotmqxstturxhvbopxzatdbcbftsfkvrnliswnlcnfjgztqiilhtrfshrczhwrdgakwyefdcregeybckvuxgefzqitllufrcrdohjrnvsliidhotpfegytotpjgrgvxzuxxmfqsslvleslloegsqiniesztdgqoniyperoecuubmkniqxdrpkautdiepqsfgyeyhcpywybmqpicoxjktqlhdowlzqnkywhbcszahuhdzusjrlytjajkhbekgkhfjhyehaboyodfyemvbdpumpwpepllwnkglmeoeutllgmnefdfsjjrhwncdjuoglolgnigesopzcitzmublikzvbtuwfmlixiouohygtpecaqiarvlvjquhwgskivqnugscbhwbfwczbomoyopkmcfawkptowxhcoinryagwzwqzrcvwqypuvudtqqootykyxjszfnwamnnawsrzxujldwqecjvgqasndukzkhjlglzafuuzkpdopxvzbfztszdbixxdhwuvtmbpgagodfvbkndlfuqsszddpucpcnkkafgztnthrhtviyusxpmvrmxehzihiloycjtxitiysabkskfgadgtanjgwtrtjblxdrpffwxbxxverdeaocyvtbiuoswdfslupbvvljskyyafmafpordsrcxgwhsrzzavxrxyalsltbgpazjsnzszbodpckrbgcswoisqpxrdqpyrfrkmzgnxkmwrsrjpbxdsygiavwrjtsvdrqcqdvcksifjmkxgjjbdhhonsmeeugggzwaehrkksqyuxfiujqzymvshundzkwufqduffudyiwgsmsgpcjcjcjoifgrtzcwzbwugksbjwnagrdkoyupijuususnidrwhutyumztdjhkplfoidxcpecjonvsyyegvgqkkgiftkpoiilavundmhfvylqyvmrsumbilvwuavxaprngmzfjmxfvbvifdujwkufbgdxvtonpbixlgwhaqywmvywqffjxemjyvimpdspcypuybsyplwpmhmoxjqxbbthncmpgtupboupshzwcftfezekfeqbtnznmicivderihfnhzgwnlngzaxmfmguhjzbrjnuvhfcbwbmikizkcrsuosadtdxtvybloevrgbvbqapepuoagfnbghvyczrfuoxfryilptnqvvekkiafdpqxbeebaavhaxodgignoovzdslkjvhhbfrcbyqkxdfpycxxbemedznmybhnmrlbtyaslixovkagqzcrzmuuqmnrmsbczuwazwzbpqjuoztiotejzfhmjdorvdbltqfkgannctbfwspwpplzlrwpxtfknwohsjwkypnccvkudgtkgzqcgrgpuvuhbdbhpcryogpuzozmcnsvrnjnjqimdozemipvdmurucidhtfwqfvvfvdjitdnzguxfmhzpakfacbodntjkkdjlgarjpdvwcmeorpgknauhqmdkbwosxgdgffgnhmmgnmggiemabhzlthcaffclixppqpahguysacoqroiekpgiflcaqkkzothgyfseissmhgknopogzfinuchyfwjsjuiiksttqpwjlyimcjnmalpqvbtsldznqwugkskikroefgqjnvzoplgfkzuqqyaalnefuircgrhwbshxunccnrdldxybkrpwwziakhemeusnxofbqqrkguncposjyljhbpyrzuesxxanbjxmuuabbrwezrehgfwqrqyflmmlydprpfuhecyqvmnhdrgffpkfgaixkrpcrilctvthuvezrudsmlnexfnkzubgbzatfcjjguufflaixwjgvgpcqyuxwsfnowafnglteueffzratxnqgibwtvcygoppgcnblumxfavizherpzfatmrrliswqegsdykjpbzehnexbpmgebrmqasodsgxodeqfwqwnytwtbkfydtizloygnlilyujxvdqeoquovhdpsnbltlopwhjwqzzwstofvocpnmckjlwrzaxrmvbfptucbnfvpqxybsqvekqugkcjcdcdmueoovkeyisnsqlcowimxzuvwpemluweeiuesxzlbrwehzqprznyvpwsezxgvafastynbrmuqchfglcowjvhevwuubhfiormhtlrhpeytnidyzppobjeclubjigdrmjyymyxyelbprgohpberhuhcuyvpchxqqdpgdnfgtmauvwidlvmlacdqycievmjdmbplpcczwiitflemhfesyhulkgnlftsyddxpfjispiebmzafbqxxxsbejocgiigvrwmqfcganokzaurismihwnikkmsdcbmfyfcuutrogtjlttaxnolsieihxvubpcfmnfnaiswjaoumfhmivzpbrraeftyhgirmrvyczfkssdnqpuhmjafvpnttxoixiwejurkijzywvanfxvkkmgqtqytnsfntetauncecthzjxfqrafouhagkrdsuxcxnzqaiytfdiqtwxkmhuhslnditxhjmmuijagmrrkpztwwftsvedtdtqetluqmcepvisnwvsonkxqelxiatbhhncoyadghlkegavegncnzcstexayayoupgwfvxtcjncpktjivgruxslebxukudntwhaftyevccdhwodugpdrqfwpzpztvthlmhfscdumxqosrgfswgmszyqsetwvmfhxlhuwulpvcsosqrlvzklksgimahvdaoxqakuvtpzvfejrflixyoyvdyywcfakndzhrvbdkrillejoicbpmhcnvpyhcufaezunpkoripsbcyurthkvnmkkmjsvvbpbyzwcjrcoemldczdslsezavblhzoxbbyjfuhxpbckhbkpkcdmtcvudsoqzbnegohzyhxwjsjiuzdtbjbegkbrkpohrgezmtxdiaghrfrdavhidckgmmkspminalblvgbauwyznpbtfpqzjzzlvzikefcuahffddmbjqpeflwgvsqoxmbxpxadaglblgroxqwgejpxzptlzwyfuhyziahpsyjljqyzewzhlfoctchirzfoxgauqaqmgzjeaktteinwhjtkxsnogefibirkctyuxlygmrarvsjvkytfdqcqlydebagavluuwgehlvuhcbbmmkrdlbnyqwlpnkfgmjktwuwtwtgaiynackkkvsbnkjrjznvmfeehzaorkyimgemzkwjzsejtzlbrtxspqhwjfsdbikpitqdissqjjginuptmrdhhgllrmxokekfldwpgzbwyfuctfohxrhehjevtbeiprlorgbuzxoogyqdvfgiblauogzefsxjiieezxqrqqltfvpasjefjobdqwdsizqntjeianpwbyxlxuqpasjvfrccwaumnvulwzfxqqkvjazxnicvkyimzfyhatigyhinvdqswpddpesgxrhdrpajlndymewtjpbmbxzfiqhviypfdyhlkbqjszxnkiehwhiezixdomsubvslkghkkxqgxzqnrizzwssgdbkgwzivfqtpwvzapilhmxpxigjojiosnkrrywoyjppcqgmuzfadytjjdbtrxeviprznshajjoqkjwdxeouuvehkszilakgorfcgkbvkpiwdqjzanxodhancltmjbjkaixxrcwvpccmzczysfokecjsaurtwtxgdogvjwkizbyoahrbvlsomdoxskcmvnorzzsjgekmdshujurhzowusqnlzzwvzfjzpmpnphoaockosikekbhqgfsqxqwtsuwmrieviwbygbgchtawboxwkhzyyosppdptngszaouukrkqgddofeiqsvcbzbnrwebcgtriehdhvifzxfjviwooynjzugjhdjstqszleaklelphlmippragvevsbkklvhluozuehemcarroaftzihnnuadpobwmvhxiouuwsfcphevzcuizvpctdjkpwhcttehvaivdxsvesgpyovtgvqngkppilqanxyeajpjgndkrromomkqfuwvnunzdqprzbgireucpvfimiyfrsrfeaibngfxhjikrktqcjcfbobbdpqrinprlmshfzyescgoqkpyhhujgfaasggpgujaprhjbouizljenfhacaobtvbwmdvilczkugwgeytzayoxobhcwgyzwsbonvwfjfltsycnxltltmntekdkhahuvwqucmtzsnagdmgflqgpybsbsfiuxajtrjrugpxdymrmjdllqqsgcaqvuuokajeubdryouyopwnmlqqtlfwyngxybrvzhzxvqyigoqcziemctkggxynbtgnlegyygyxndkbondpofznylislptfvxngrbctfpvyxlooujbccupycdfmvmailpyosezhkrctdxdycejuvvyscfhjnhdjqetmpmdnyhhprqaezkcbjjaqbekiutcfenaahsxmheisbvvtejkpxgoocpcfozswqsswvdzprzvyyitspufrwchskadjmrisuxuhxnnhitvfkwqnzpjbhzzcrbaxqapgcbihkifiqxjvopnyelulrauegwbuqqaoscuoawirzpfeidhtwqcnujbyrynokbfajnzjtctocfepkpzisckezbtkuqbivbecenwilmccerucgcnboxpmgsoojgqtxevhvmzecvktucxbjmirmqvoiebyhkzqtouiaoojigebampbncmiaqojbkgzakijdahjmtufwcxrmjcqjfzbrwwtnctgzhztefngvpwtdnqrrevzctxhkzckugtgekrkbmglenpsknjcvitacouzqpiiumixtpfqlbvzsylurbgytsszhomhnsrcccpczcqpprcopgudufouncsynqjwwtdqnppblgwhqhldkjmdsfiqhgvpniyeznnaxduqpwfdbhhbcoisuphnbynoocelojbqvuxdcjvwxasnxejjczuvrmrpcklvcijphbghcnbevagdnqfykifozsohueivxydchtmmawdaoiywhdmhpkkhtgyvgtdbgvcedwpocfbuibbcjqpkjlzdjsbanjihuwwvmchovjgwunonvwkqjdqrjkppfekjcehismyrbwrsikxuthwtyyzsikpdloayjkwbubwuuzyueyhpnbljukmqsugtzfpfyofptdoaxwtfebwqyezclnijfhykymgmyjadsxaxpzhaiqgqkygamatbpaaaevtetyoosbwvhferwvxcwzayfpfkgyvjgakyqgouhimcyccputtsrwejwliaxewjaedfyxhhovvdwiofccjjfkcodahiafzhhcundpsdfmbxlfrldyceezushrrmbkboaneauydlhrhhqfslwsssflzsnpmtqgsexgxvupvlvuucgnvchsayimzqwhegmqvppzfnasralodsteegzgdkabhkoaaiizjhxghxdshwqxpgbpppnazfchlueyqewpazmnitxjhxlmjfwqubyfpzrxkcjdxsnvdntqkohgsbrozewitmlyxiscjmgyprgtgkqzwryyfdptapcnuhusbncjyusndwbsxuwxlewjcmskculeinswcagtyomdoaxoqnirgsgvrqcsofzzsesgdjmwrnyybjesxrebxkjappjtrlloiruslbypzparqurtqzhnbeiraojtebexzzeofeqwiwnxdrvawbsnhwawncywlyrvmuwtdiyvevuvvndslhgrussnpzyqlmsjhzeyufdrbqkqfpdnnlhbpsgyswrzdfuzqhvftadiqeslgbwcslpuwqkdmkwqdaxuvuthcggpgnoeardqnhrotewuypozgmuzfxhqinipomfkydmcnhifpmrktzqlncoucbpelwtsrcjjwphnglgcgsgqelyqbeymotiifnybgatrrpbowpcsegimvqkmabnlbensjotxxetwhosblyxfitocmaokoadwjlvkgzoreyjkrpdohzmxljdrdzjqjojvbiyhokaxyxfikqsthjoamkxhkxymsgvklzvnnngjasswsbyfdabvfyjhpijkfwfiowtdhjciirqrbrwdukstrlirczvdzkkshfdkioucqtfmihpblqxwmvpxetweoifqiypthdfykdrkbwwcuyuygpqiqjadwypxtdphavaedauplrxwjxaitcoetjbwvhpsizvensphpexdvqjcxldpgizcysqljarawvrpnozhvslfuttphheiswsaxshbqacocmdkaoqnszfcdgpdqxezvwkphtsubkohnpgrdbjutfejpobxckjtemroeidwyzduxvbzdpqxkppvgusikpgozxttvnpojlreuqnpmjfhbmninaqzlgbvhbufgiuadefemupyrccczupdhsmwspkhhhaqmyalgreqrimamsqfbsvewaiebzffbcmyexchfycyzubexlgdhdafbujkbosnicuahvuajszoqmwqpbucusvdrteemrwvshfeuecdaswheuyynczjkinsnwxxxibgqcgcaxmmvdqpttyobhwgsxbuokjppdxyvqqtenjfbdfcrbdzllvhrlnzosfhsmyknjddmfblggrbuhgkpxxgupdbzkigbvemtpmnrmowkrdzegfpxplcwgybdknmbwyoyzmhvztoogkmrluykcrwioyhmqctnfnhngbmnbvgnfwtbvtudefcxvuylmchgnvyorxdywahexmgfjifvitjsbrbngoetpnqgzaiplpgndlitifeclroysuykbotgbszfnkhoiulxahjjwtxxfmozfunexiehijvvxtzwtdslklzaytplnovuvycxirfpdkbuuwsmsmqoqjfoodvbaavdraxocjfgdmldvhdylgdbzopxfgqsfbwatyuzusjpbfeqtdwhqmmzgtvokrtvkhkvzzxyjyoalgzngofigysifhsqwbcpdhvwvgsuefqjcakzujhnrkftzbiqevokharafvehvhqocetzwyjxbuwppflibuzgtifnyczhjedujdiyrqnbscqapnwulyoosuddqeflcrtbukvacifqivlonjcvsovzzhmnmoufatkqofjmhjrcnbkcnzaayzokqgvwzkjybnfioqgtkslxzfmyqldbofuyfqsevyolaumcjsmfxpdrulslchkkbaxrwjczxswhaxxumjkicxnvhwtxonipuogiderovcrhcyrczcubwgtyeeyvueazxseuhupjzxesveckigahupcdxlztbphdhdwvjtexivbkxyrmdsypabpqxixbnseiibnauhnbxqlkcwrvrmtdpbealttvvelqifmkfsjzhnaxdrgrfljlfrnqtcozuilmgudlzblnorriimmmgydrpostalitfjdxtdzanqwxfmdvduvpjtmbsttaegjltahgwlvhumxzjcrmbfbqxehmbvoksjlfrvnmchdcujqiazavyotzcksxrtlwzrbxdvdqfordtidhbtdjrpxplxhwoeutsevzvfthpscglynwujnjqgonhlojbjhcqtagesfxoqjcmvvyapmwnmegrttcauutfkjgqbgkomzhdnfxqbhlrmnznnqljffihmfxoziojgltztgyohzaxrqzvxnlcwegiodkiipzfgrnpdzxngspecqbdsdibrodbdbzezbgzfnbszvamskuojtlszltgbleebgfcriskbvxdlinojdqnystcszubjggalzaapkhvwslcgypmsrjydmnflbntzbykkbfaixyhuxmehrvxtdvgjimekmbsnnmkppoqmitlmuvadzyibbakinnaelbgpjnyvqjovucxpmsqtxiaxdyzftuhoetpvvndjqqdtauurgatbdshriepepbpquwpbppfqccgnbbmiaosrwvexrgrpvbnhanujhzyvvpneqexwmtdlurpdmhgivbtourwplhcwxikyoqkgmfyrtagybcgipwrmcooirzpaminzgfdnftdkgcdoemiatlwmclzbfthmkdjtainbbhbbtpjzybxpabusdnsbomrrwicghclcyhwmgknisoppgzwnfdiqtxctvitpujafnagwtippdmbfjcempupwdghhcqngyeszyicncylpfwrleyhjrxkoodcjclwqpcwosoirkchvieljwindydeiebtcouwxtiqsitutxjyzccyusxyrqopdbgvxgxvjwykgliphvhfoqxacgslyvzxczrrgvxptyndcinoecxkmdfuvzwukskhwgcchczewwbzsrcalgjxxkdaawwemrdcnsqpqoqfreelretvrtsuaunbsejbynikzslsvorwabfnkdnurzpcyxkkoqfonvrbwnoxziwuzgyqlrduaeqeqrxppbajzbdchrzwogyoevzfizrwsdvdctxkrzlkaqmdbeqchnxuhitdczebntajmypyyoxcmdfcegpnxwcoyelfpppfiupzknpweyjkddeinihrakkguqfdyfsapabsykvaeqcgehwwkhjhfeumpfkdmeuptxoabccuwusteyjzonatqqejbcrndcaadeskdmdbrimrhnfradkdpbnyudldgiuboguwslgxczetqvmyhcjoqamgdzgmclemtimaoroartgbkwgnegxoordytopfsakgovafuclbjvcfypkpkoqlqysepkkaqmtcbwtnqkdbqddhzenqkneapjqxmboiaeifwivjqswfplbmtmvlqsbhhbgnrpaqaznoqiblvcvrylsmvvtuhlyvonb";
	EXPECT_EQ(s.checkInclusion(s1, s2), false);
	EXPECT_EQ(s.checkInclusion("ab", "eidbaooo"), true);
	EXPECT_EQ(s.checkInclusion("ky", "ainwkckifykxlribaypk"), true);
	EXPECT_EQ(s.checkInclusion("park", "spake"), false);
	EXPECT_EQ(s.checkInclusion("adc","dcda"), true);
	EXPECT_EQ(s.checkInclusion("adc", "cdda"), false);
	EXPECT_EQ(s.checkInclusion("a", "a"), true);
	EXPECT_EQ(s.checkInclusion("a", "ab"), true);
*/