Algo 200 - A Substring

Writers: Jakob Degen and Jacob Edelman

Find the number of sub-strings with the following properties in the given string:

1. Length >= 2
2. Contains only A's
3. Bound on both sides by either the beginning of the string, the end of the string, or by any character other than a.

For example, lets take the string "aabaaacadaa". It contains three such sub-strings, indexes 0-1, 3-5, and 9-10. The sub-string from indexes 3-4 is not valid because it is bound on the right side by an "a". The character with index eight is not valid either, because although it is an "a" and is bounded by the correct characters, it only has a length of one.

The string:

caanqaaeamdwaagarapabseaawaabawaoaalaaaaaxxaapsxeaagragaaadawaoaanaawpqatdaaatakwsaaaayaaaaealabjxaaaeaaauamjawnsaataaaoaaqaxaaaaaeaajrahaaaaaadjaaqtewhspaaaaannaoaaaaaboaaaaaaaaaataqadihaaaaqawwaaazoaxaoapabuzwaaaaaaaahlaauakaaiyjavwcaasxaaturabanuataoikpkaoalaaaaaaafgaalwuxzaazaaltazjdaaasalraabaqjmaaadaaaaaaaaiauaqbajaaactaarwrcavmaaxxaqrxaaaaaaaeaaaqaajafaaadaciaaaakadraacafaahlaiaaaakefahalaaparxaaagaacnoraaytaloasaadaaaafataaoqarcazjmqeafajgaaaaaaavvaaaaaiaaaaiaaczrbalomaakgilacaayaayaxwaotaarlaxpaaraapaaaswhxxaajeagfaaaaeaaalaaaaeeaatoamayaaauaadaueccvaauvaakowasxaaatgnwaawtrxtudppfaaqfypaaaaanraiaaaynagqqaabdaayaaazaesasaaaaaaoaaaaacvawcasaiaaaavxafaqeaaadaciaaanujgxamxiaadazanaamaygabwrfazalaaawkpaalsaafiiataatavvaqaqzdatyaaaaanpsaaaajvaydxacyadaolabhocaaawaniniuaaakaaiaaanxaaxaccfaarlaakaabenevaaacaydaaxaaxepasmaasadabanaaafaalaladaagafaaaaaahagnixwemathayfagaxapkaaaafaasaacawaaaaackawamaaaawaatnaaoaaatbaniafawaalkaaumqzaoaauaamazaztamvdaxdaraeasaaaaachoavaaaqaajwaaaaaacarlaxaaapaaaaamfaaoeaoaaamapkacamraalbnavaaaxiaqazaamcmanagaicraawaaascbmraaavabaawaagqataazuaaaaakawxwazparaaaaaaaaasaiedhfaaaetaaaapaaapiaaaawembhmafalgayaaodamqazqwaasdeaappaacaarahnalaeaaaaanasasbzaaaaoaraeaazhaaevoiaazpypuggeayaapanzakaaaavzaacaaraaaaaaaxsvyacoxvttzgtbcuazxkuaaaiflbjzaaojaboxmaadkaaakzsbxaaaajanaatgaaaazarfaawujasaanxazowlfaayahaaaaaabdoayufltoaiabayaaafawiazaqaasaafchifgpjuvauaaayaaatvaxaaeaaharrazavlayaaaaaaagxcfaemvyaaaaaaulxajahazgapaasagswmahaapbaaafnaaywpagqiauaaaavbmgifaweatvaayhaadajaaaaragaminaafixwuaaexaajawzaazlaxastaatmdaaaaairfnraaaaaaaxaafgaattgakkaacioaabatahfqabmvzfzafifsbbnaaouaahalaahuaawaagataamarjgaaaamianabhaaaaaaiahtpxvaaaaaaahaahtgaaaazvafaaaavzkamalawaaqeaaaavgjkanenairaalazaaaayafsazaacodeawvamtdyaaaynaaxaazvssadaqdvstaaolcsecwszzaajahawajooaahgumavaabriwaazgrtaauaxpaaawbhaberaqltaaaaqaaaaxayldaaxgakmwmaaxxayualfaaijsaaaazxpaaaewcngnaaaypvmayaiaamaasaaakattsadqclclafadaaaadsnwdnaaqasataabasaataaaapajqatuakaygaaoamatgaacaaaaaljwzaaaqajafanaaxaagxqaaibgaslawuadeaaxbaweaxxaaaaesnaacatahaitatqsabkaaaaatlajpavaaadlnvzaeaascaaaahqmatanapciszqefcalacjraamhaaaaoanaganaaaaacaqcnaayaawaagazaayyaayjagasarbuafzpmpqeaohaaaglidaanrheaaaabnnaairalrbjuzaakaabgaeaadaaetaauaaaaazaadzxaaaagavazehulaauazvcaajcaaaaqgexaaaaajcirxauaahaoaaahohaanaayoaalukbaauaaaaioaaakcobkoaqdvalasraaawuaakaaaaaadamsaaaaaqakaanaxaaaiwaodazaanaaaravbqimznaataaesaavyqjakgabaeaiasamapaaaalwzaikpbclaaaacalakusaapaaaaqnaanaaahoaaaecaarwwaaaabxaaaaaepalaaaaaaaxaxgamawmalaaaaanqeaaaaxaomajaaaiavaaqxwaazaaaaaaaaapqpaaaaaastgdydwxaalahaiziaamauayaqaxyryaizkaefuaaaaaaaeaaanaaiaaaaayaaaaaaiywaaahaaaaajtawmanmadayaaawaaaaxagaaicaiagaaanaaakaodapaaaaabaaaaaadauevaaywbaaaaaaaaaaygaaawaazimwasraazoagvzpaabrnmlhqghhoaaanbaaanaaaaaqxauaaataaaabaahaaaafzaawaapaaaaaarazalqhobgzacazasauaaaaaujafowabywlaagaaadaaatamaaagnpmaeaaaaahmmxapanaraagsxoutbaaaauaqamlazaaaaaaaazaalnsacxltaavaaxpldaqqhapasmalaasutapuasaaatuloaaadaizmaaaaaqqyalyopwakaayhvyaaaczjeauavauxypyenmaaqiaaqiaahuaaakaauja