Problem Statement
Definition
- Class:
- CountingCommonSubsequences
- Method:
- countCommonSubsequences
- Parameters:
- String, String, String
- Returns:
- long
- Method signature:
- long countCommonSubsequences(String a, String b, String c)
- (be sure your method is public)
Notes
- A subsequence should be counted only once even if it can be obtained in more than 1 way from any of the input Strings.
Constraints
- a, b and c will have between 1 and 50 characters each, inclusive.
- Every character of a, b and c will be a lowercase letter ('a'-'z').
Examples
"call"
"accelerate"
"candle"
Returns: 6
The 6 subsequences common to all of the strings are: "c", "a", "l", "al", "ca" and "cl".
"topcoder"
"topcoder"
"topcoder"
Returns: 239
All possible subsequences are shared by all three strings. Note that the letter 'o' is repeated, so some of the subsequences may be formed in multiple ways. Each unique subsequence is only counted once.
"no"
"correct"
"answer"
Returns: 0
There are many subsequences that are shared by any two of these strings, but none that are shared by all three of them.
"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb"
"abababababababababababababababababababab"
"aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb"
Returns: 1725660
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Returns: 50
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"a"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Returns: 1
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
"azazazazazazazazazazazazazazazazazazazazazazazazaz"
Returns: 0
"dlafjofjaoeijflakjefoiewjfo"
"asdlifjaoievmoaiwemcoaiwemcaoeiw"
"asdkjfsaocmaweicmaoiewmcoaiwemcoaec"
Returns: 13988
"asdlifjaoievmoaiwemcoaiwemcaoeiw"
"asdlifjaoievmoaiwemcoaiwemcaoeiw"
"asdlifjaoievmoaiwemcoaiwemcaoeiw"
Returns: 3815014845
"qwertyuioplkjhgfdsazxcvbnmqwertyuioplkjhgfdsazxcvb"
"qwertyuioplkjhgfdsazxcvbqwertyuioplkjhgfdsazxcvbnm"
"ertyuioplkjhgfdsazxcvbnmqwertyuioplkjhgfdsazxcvbnm"
Returns: 70368748371967
"qazwsxedcrfvtgbyhnujmikolpqazwsxedcrfvtgbyhnujmiko"
"poiuytrewqsdfhjklmnbvcxzpoiuytrewqadfhjklmnbvcxz"
"qertyuiopasdfghjklzxcvbnmqwrtyuiopasdfghjklzxcvbnm"
Returns: 773429
"qazwsxedcrfvtgbyhnujmikolpqazwsxedcrfvtgbyhnujmiko"
"qazwsxedcrfvtgbyhnujmikolpqazwsxedcrfvtgbyhnujmiko"
"qazwsxedcrfvtgbyhnujmikolpqazwsxedcrfvtgbyhnujmiko"
Returns: 1125899705516031
"z"
"z"
"z"
Returns: 1
"ujmikolp"
"rtyfghvbn"
"wsxedcqaz"
Returns: 0
"rtyfghvbnujmikolp"
"ujmikolpwsxedcqaz"
"wsxedcqazrtyfghvbn"
Returns: 0
"abc"
"bac"
"cab"
Returns: 3
"zhz"
"zzh"
"hzz"
Returns: 3
"sduvniesurkl"
"fdlxrdxursduvniesurkl"
"fdlxrdxur"
Returns: 9
"abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"
"abcdefghijklmnopqrstuvwxyyxwvutsrqponmlkjihgfedcba"
"yxwvutsrqponmlkjihgfedcbayxwvutsrqponmlkjihgfedcba"
Returns: 5550
"hqghumeaylnlfdxfircvscxggbwkfnqduxwfnfozvs"
"tkjprepggxrpnrvystmwcysyycqpevikef"
"mznimkkasvwsrenzkycxfxtlsgypsfadpooefxzbcoej"
Returns: 282
"vpvaboygpoeylfpbnpljvrvipyamyehwqnqrq"
"mxujjloova"
"wuxwhmsncbxcoksfzkvatxdkn"
Returns: 8
"yjyhfixjswnkku"
"nuxxzrzbmn"
"gqooketlyhnkoaugzqrcddiuteiojwayyzpvscmpsajlfvgub"
Returns: 3
"aaovlzylntrkdcpwsrtesjwhdi"
"cobzcnfwlqijtvdwvxhrcbldvgylwg"
"usbmbo"
Returns: 1
"xtlhcsmpxohgmg"
"keufdxotogbgxpeyanfetcukepzshklj"
"gggekjdqzjenpev"
Returns: 3
"gxiepjsrdzjazujllch"
"bfqmkimwzobiwybxduunfsksrsrtekmqdcyzjeeuhmsr"
"cozijipfion"
Returns: 6
"eddpszrnavymmtatbdzqsoemuvnpppsua"
"bazuxmhecthlegrpunkdmbppweqtgjoparmowzd"
"yoxytjb"
Returns: 4
"hawdydcprjbxphoohpkw"
"yuhrqzhnbnfuvqnqqlrzjpxiogvliexdzuz"
"srkrusvojbrzmwzpowkjilefraamdigpnpu"
Returns: 24
"hgxpqnjwjmwaxxmnsnhhlqqrzudltfzotcjtnzx"
"glsdsmzcnockvfajfrmxothowkbjzwucwljfrimpmyh"
"hzriwkbarxbgfcb"
Returns: 45
"eyhjugixw"
"bvtrehbbcpxifb"
"vfbcgkcfqc"
Returns: 0
"cotzgkubmjrmbsztsshfroefwsjrxjhguzyupzw"
"eiqurpixiqflduuveoowqcudhnefnjhaimuczfskuidubur"
"swtbrec"
Returns: 10
"ykabfcvkdzeztoidukuhjzefczzzbfk"
"dpqzikfobucdhthxdjgkjelrlpaxamceroswitdptpc"
"lifkeljytihrcqaybnefxnxvgzedyyhngycdrudmphmeckotr"
Returns: 825
"ospofghfozqvlqf"
"wwkmfxdyygmdcaszsgovsodkjghcwmbm"
"rmhuyfyqgajqkcklznay"
Returns: 8
"qkqoyzwm"
"ubzazcpkhktkydzivcuypurfmbisgekyr"
"zvxdhpoamvafyrarxsvkhtqdihersigbhzjzujx"
Returns: 7
"myspnaraewkegjc"
"vhhrjvbjtsqdjootgpknfpfyc"
"fieowqrww"
Returns: 1
"pzsqmetogepspxnvjiupalyynmkmnuvkl"
"secdwracgf"
"zkgipdfodkjmjqwiqpuoqhimvfvuzwyvijgfullkjdu"
Returns: 1
"sjafbtlkmfqrmyjfjnhhssqctydteamdcjbprhtnegyiwx"
"cjwlgrsmeaearwtvjsjba"
"iojlwhypnvruiho"
Returns: 11
"wkifygtydhacwyhsgewzmtgonzltjhg"
"uhnihreqgjfwk"
"smtpjhaefqzaauldrchjccdyrfvvrivu"
Returns: 11
"eegfivdrcygurqdredakubnfgup"
"oqylobcwqxkzmausjgmhcmhgdnmphnqkam"
"urktrffaclvgrzkkldacllteojomon"
Returns: 44
"rqyjzginrnnzwacxxa"
"drwudxzrfusew"
"tboxvynfhkst"
Returns: 1
"enaumnddxfdmvzcautdcckxaaydzsxtto"
"bgqngv"
"pjgojoglmkxgbfcpypckqc"
Returns: 0
"bd"
"zwrxbz"
"qrlxvobtwhxginfgfrcclmznm"
Returns: 1
"ugwwbsqfcihubsjollmsqsghmcphelsotflbgsfnpcuz"
"rupchynvzhc"
"qugriwniqxdfjpwpxfblkpnpeelf"
Returns: 7
"mtkuqpzomwnlmbupmktlpt"
"dmpdsydsgv"
"penemwborifsuqhceskmkhssmv"
Returns: 2
"onwafxwhgbibabvqopqfoviussqfqwehtxdzujtlntxmrjxx"
"tlggkytbiolydnilqadojskkvfxahhjmbocljarintd"
"cldvdxropbyjzwyyojuothwmlvrglfzdzdbtubxuo"
Returns: 511
"fv"
"crswsaznmoijoivvgobqpnckwvnhkebmtdhvygkjisux"
"atmuud"
Returns: 0
"bhmknhfxaxqxkjlzzqtsjfaeedfuujkol"
"jo"
"kdvfepvlhvhrwtfdukxffjpss"
Returns: 1
"yxlijjhevryxozbafpfmowgrgonuatdqlahyggy"
"jddjhmltedzl"
"dsrkeutgtnkntarjkpxinovgzdt"
Returns: 11
"unwooxvjjmpsvknhkwjopmmleb"
"sucvzqlyqnwcmbvbhrmlowpjbwyvwtgtoqnmicxap"
"arknnxtuufarzr"
Returns: 5
"sdqwsmtcjghecqudosrtjxy"
"ayk"
"rxycrxuwjxnpqjnbkcpdmok"
Returns: 1
"timnohsski"
"zvpiczzvk"
"fexqflcvwf"
Returns: 0
"gxdqrrxulefhuuvsyyxlwadyjviwrusy"
"ntszsynyatatdvzucbwlsoaukbkazzmh"
"ocdvkdxwbllkrlvprbgaxrquedjcwtswx"
Returns: 76
"opiprolmvximofhtpxissfvsrdzrubkrsmpyswslxbbh"
"wsodjbssjxmnbpbhvzpdnreqgwimyexawsjccjkazuncfm"
"rpnlbetnqksyewefmxucjcjkztewiydozebldgvdg"
Returns: 219
"viyot"
"pzjienu"
"zikwhajvu"
Returns: 1
"oaxmemhdezebpsmaydiueqfjosbd"
"kdkwkqimidywopotbhanghan"
"bxlilrcixorardrucstoijr"
Returns: 12
"bfjobxqzfjstrkfbiijbxijweh"
"pqdtlbviasunmiwseouwnr"
"lcjxuyyqxiakrsqbrwxuuiunugs"
Returns: 27
"zpevxlujyjjtcfwuzifgojxcmgelzekbvchqtvgndlyf"
"fynebmmsgfyycxypevqfdlnurpscdsqlqghrhbj"
"gxlvyjpikenhwptqzxedxjtwkspexaqitqeceosm"
Returns: 216
"sbwrtenisxjljbtbqcfjtyeubdqqkbyiodz"
"ojndbzitrinvrutsaqjvjbqslprlywkza"
"cjdbgteipfsblpnirjnwrwambepndggai"
Returns: 151
"lwlxijrsnltiiazobpjqreoumkgwyoidnacdaqfesphkxzwr"
"vfifucvcltlbyxsnrxatnkvrhvwsauhdqmrbzuzatwdclygpn"
"nwqgofjhlrrltnwzdxbwqyeqegsgabofxrblglmvbnan"
Returns: 3492
"dsblsvphltlzhlzpskhhluodsevnfti"
"pyzkwnijljaddfghpfkbhpmdqbujh"
"uhkhcnnyijkzwyuqmhutbrzubprkvt"
Returns: 41
"opbvsuoloow"
"xncxodjvd"
"aebphllamemq"
Returns: 0
"aslwzuhdckysilpdgvgzkleyixwlknbrnqjtyk"
"hlvibrmwzhmdcvxtrzlcswvlxfrxlxhqgwju"
"ffjxjrvzlvpforcprioupfskxtsxrxyukxsq"
Returns: 233
"ksblmfcriplqyvtuflnj"
"yuhgtvmbruvgoeqfvdnzg"
"yfjklegqvyzuvzubqyi"
Returns: 14
"lvehevcafginwacbglnukgbmljoquv"
"eyynrtwifmhcwfqebafnnuguenvef"
"kqxjvlyyiixxexhalrpoubsslvlfogxec"
Returns: 110
"ridcljheuwqqwlcwjmesilpzihuxorke"
"whamudwxbkzjjoijstnofalsslkbbmunpxbj"
"bdenxkttqgsrigxyguvjaonvlhljtuhjdt"
Returns: 110
"fbyv"
"tyimm"
"moyvb"
Returns: 1
"kcevavodumtgsfpmcjbtwzwcfdyrlio"
"kaoahlmuzmilvmphksblmcvyuqvzrchbif"
"ucrmltejfltcwfgujpzeyqnzvosontqk"
Returns: 70
"ueqkyubsxnetlx"
"yeiuzqnhdzjwddhb"
"vnvmktnuzvgzetb"
Returns: 6
"eoxtzbyetyzebdnygqgljwtdflrutyb"
"qawnbozefmzlakezultgyordcjtlsunxhrrp"
"dseggppxcgqqgpfxxyabfxpeeqgwgonbwthl"
Returns: 122
"gngzfzedaivgmsnznqcppkyrtuoxcturebtpg"
"wvpfffrivrrcvivadwbzfxivlutspxtrdrez"
"evqvbtgsqzxunsmkhtkzcdedrzrztmllhxjyull"
Returns: 219
"qgxmamusppumvihabnwzgtovaieegecpbamjdpxge"
"npsimbwafjelprkatdbpacnwhymhwxvofdhgrckb"
"uuowxzsshqmkchexlcemhmmesgxonjdumysktdsge"
Returns: 428
"zpejmzrsnazpxqhwozwhhyjqmoprjykvcnsyy"
"rcqsrardxaqjoujlktmbbhrdsyvefkejzgeor"
"yessozuthpcybibcxecywdasdtrrlspclukisag"
Returns: 146
"smafisvrcrkiwrdhgbuorhu"
"zawfimetqfztbodhtqtyhas"
"ibntqobukwycteaipokyteodk"
Returns: 18
"uuuneuomzfeywplxwjibdmwbgaxcql"
"arfjjuizhjgtkoehdoquqpykzsaqub"
"ngaogsjzkgxkgwjhcwqyklihas"
Returns: 38
"vuerusphvoallomynlkmfeozexnu"
"rdkuvslbfpbakybsoqgiidoohnugm"
"ftxyrzlsowfldkrgjyqcxiakpqoyxcbq"
Returns: 97
"fifeiyvqszndbdbrljlxwlqphrzsgsvkuzlbinnxwruoqjfd"
"dceeretnpzkyohtgdrgvdgfbcmdhoergjatziblbvrjofwak"
"hdyjfxatdqwnguisrgkolfafhkdnbekcnkkwtdnvxkqns"
Returns: 1393
"lnuoauxhsipmfefofrycepqq"
"htgaxhwyifaumwddvil"
"qprlyuycygjrzfbjhbtfd"
Returns: 6
"pxw"
"aykfvxd"
"go"
Returns: 0
"lgdvpsyermtjhofwmdtgaadsatnvoqxmrqqv"
"hpayoannqzhxvciqtxkxybgwsuoakvwpgxw"
"tfbpspzznreuluebuyilvdohiwfwzcgjjr"
Returns: 99
"gcdlx"
"ackzph"
"jrb"
Returns: 0
"echhgddefdhhcdefdgfeedeegfegcdchfghcg"
"eggecefddggdehghdecfeeehfdchegffedhe"
"eehhedfdgddgceheffhecdehdcefgfehccdh"
Returns: 510710
"rqqpqtpppsrspqrrtrqrsqrrtsrqtsqpsoqpprptpts"
"rrprqtoproqrsootqptrtspspospqsrqqtqtrrt"
"tptpstssroooqossotprtospootropstrtssopsoso"
Returns: 209460
"kinminlninlnnjkjkkilikmjkjklknmknkjnjnjililnjjjmi"
"jjkinjjmmimnjnmlljniillimkijjjjkimilmlkiljimmil"
"lkmkjkklmkkkimiimjnilnnlilinljkmmimljjmnnimlmikk"
Returns: 2951503
"kkjlijmmkjnnkjiilkkjklk"
"lkljkkmmknjjmmkmilkjnjml"
"ilmjmkkjjmlmmlkjllniknmnlji"
Returns: 4534
"ustpsrrrupqtppusqttqqspsusrqpsprruqrtpqtuusqttr"
"ruutqrsrrqprrtrrrqqqssurtrrusqtptsurqttrptprqqs"
"utspqrtrsrrtusrqqqurtrqsqsqtuqttrrtptrtsqstp"
Returns: 14186343
"defgiggfgheiedigifdigddideeiffhfieiggfgdeidfid"
"iiiffieeiidigheeieeiidiehedfeiidehggifihigefff"
"ehgieggehfifdegefgdedehghffedifhgeedeiiheegife"
Returns: 2527138
"gkgfif"
"iijkk"
"ji"
Returns: 1
"rss"
"qrsv"
"ruruq"
Returns: 1
"pnssrnqnnsnqpornoosnoq"
"nppsqnqppqronrssno"
"rqnqopoqrnpqoopossp"
Returns: 511
"ljoklkmmollolknjonkllklmnnkoknljkomomkmkjon"
"ollmljlonmlnnjjnknlloomjjmjmljnkknmmmlkj"
"onjolljmkmnknmjnlknnlmnjmokoojkljlkkllokklk"
Returns: 445882
"pqsrrqqoorspqorspqqorrp"
"rrroosqnpnrossprnronosn"
"opopnqnosrprrsnnosnponnn"
Returns: 808
"pmmpoollnlpmommlopnponpoplp"
"lokolknplmmpppnoomllkomlnkmkpn"
"koomnmnnnpmmpmmmnlppkollnpp"
Returns: 4126
"rqoqprnprnmqqnqooomqnp"
"nnmpoopooomrrnmrmnmo"
"qonqmnmnrpppmmnqro"
Returns: 164
"utvvvutvurwuvtrsuststrruvrsuwrtvrsstv"
"trtwuutttuutwrttrvwursrrwssstrrrtsvws"
"stvvuuvrvsuuvssvvrrswswuvtvtsrwsvtvuuwus"
Returns: 92293
"zxuvwvvxyuzyyzyzvvvwuuvxyxxyuywwuxvuvwxxwxyxv"
"xxyxvuvvyxxzzzvuvzvwwvvuvuxwuxyzzzyuzwxuxxzywwv"
"yyyxuyyxwzwyyyyuxxxuuuvxuzuwywwwxuxwyxxyuuwwzxzzw"
Returns: 816464
"qppmmq"
"qqrmpp"
"pmmnqnqrn"
Returns: 4
"hhfifehhhgigghffigheeihe"
"feijefeheijhhefjefjf"
"hieijeefjjeefhgfgihffh"
Returns: 344
"xvwstvwtssusvsstvsxtutxxxxuxtsvxuu"
"tvusstutvsuxsuvttvutuvwuxvtsssxtwtwvuv"
"wwtsvwvtvwvxsttxtwswvsxsxuwusuxuvxxtwst"
Returns: 50757
"wxxttuswtxxxxttsvu"
"vtxwvuxuvvuvusvvtuv"
"xuxxuuxuuwstxxsvtuxu"
Returns: 185
"nrprnoqmprqqnqnqpppnmmrmrorpprqnoqnpmomqpmoq"
"nrqpmqmqnrrmnppoomonpmrppoprqnpmmqmnpnpqrnrq"
"mooqmppmqpoopnrrmmoqrmqnnonrnnrrqormmonqnrqoprqn"
Returns: 955485
"nokoppmlkllppmklokmok"
"pokllnonkmnlpknlpkmnnll"
"kmpolnkpllopoppmnmn"
Returns: 531
"iml"
"nmijjn"
"jik"
Returns: 1
"eehdhhegdfehggfdhhdhhgddhghede"
"hiedhfghiefeehdghgehfggiiiei"
"heiegeddediighifhedgghheihgfdh"
Returns: 11383
"jjikkffiggkjihfgjggfkkffhifh"
"fkghjghfgjhijfjihjhjfkjifjfkj"
"fjggggkkkgkjfjkkkfghfjhk"
Returns: 2033
"nnlpk"
"lkookmkon"
"olmlkolp"
Returns: 3
"qrpuputsssqqsspqtqptquttstutrqurp"
"qurussttssssqtstuppturttsususqpprr"
"qtqqqtsqpqtpsutqrptusqssqrstputu"
Returns: 32757
"moororqm"
"nopq"
"nnnn"
Returns: 0
"ikmlkilijmmnkllnjjjnliimimj"
"mlnljmnkmkljmlnnklnlkinmin"
"lljmljmmkiiimjijjikklli"
Returns: 1213
"utuwttuxvyxwtuyvxu"
"ttvvxyuywywytvxutuwyyw"
"wytyytxuxywxvwxtutvxxv"
Returns: 935
"ggheiefgehhiih"
"ieiefdhdfddeehhfhig"
"ehhfefidgifihhf"
Returns: 83
"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabaaaa"
"abababababababababababababababababababab"
"aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb"
Returns: 1509767
"ababababababababababababababababababababababababab"
"bababababababababababababababababababababababababa"
"abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab"
Returns: 24157815
"abcdefghijklmnopqrstuwxyzabcdefghijklmnopqrstuwxyz"
"abcdefghijklmnopqrstuwxyzabcdefghijklmnopqrstuwxyz"
"abcdefghijklmnopqrstuwxyzabcdefghijklmnopqrstuwxyz"
Returns: 1125899487412223
"aabbaaccaaddaaeeaaffaaggaahhaaiiaajjaakkaallaammaa"
"aabbaaccaaddaaeeaaffaaggaahhaaiiaajjaakkaallaammaa"
"aabbaaccaaddaaeeaaffaaggaahhaaiiaajjaakkaallaammaa"
Returns: 113332600026
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
Returns: 1125899705516031
"abcdefghijklmnopqrstuvabcdefghijklmnopqrstuvabcdef"
"abcdefghijklmnopqrstuvabcdeffdsfsdfgsdwwdeerrssaas"
"abcdefghijklmnopqrstuvabcdefdfsadgefwedsfsdfareers"
Returns: 7207905427