Statistics

Problem Statement for "OverlappingConcatenation"

Problem Statement

An overlapping concatenation of an ordered pair of Strings (A, B) is a String S such that A is a prefix of S and B is a suffix of S. A shortest overlapping concatenation (SOC) of (A, B) is an overlapping concatenation whose length is as small as possible. For example, if A is "cabab" and B is "ababc", the shortest overlapping concatenation is "cababc" (all quotes for clarity). You are given two Strings A and B, in which some of the characters are known and some are unknown. Each character in A and B will be a lowercase letter ('a' - 'z') if it is known or '*' if it is unknown.

Assuming that each unknown character will be selected uniformly at random from the characters contained in alphabet, return the expected length of the shortest overlapping concatenation of A and B.

Definition

Class:
OverlappingConcatenation
Method:
shortestExpected
Parameters:
String, String, String
Returns:
double
Method signature:
double shortestExpected(String A, String B, String alphabet)
(be sure your method is public)

Constraints

  • alphabet will contain between 1 and 26 lowercase letters ('a' - 'z'), inclusive.
  • The characters in alphabet will be distinct.
  • A and B will contain between 1 and 32 characters, inclusive.
  • A and B will contain the same number of characters.
  • Each character in A and B will either be contained in alphabet or it will be '*'.

Examples

  1. "aa*aa"

    "a*aaa"

    "ab"

    Returns: 7.0

    The 4 equal-probability possibilities for the shortest overlapping concatenation (SOC) are as follows: A | B | SOC aaaaa | aaaaa | aaaaa aabaa | aaaaa | aabaaaaa aaaaa | abaaa | aaaaabaaa aabaa | abaaa | aabaaa The result is therefore (5 + 8 + 9 + 6) / 4 = 7.

  2. "**"

    "**"

    "ab"

    Returns: 3.125

    There are 16 possibilities for A and B. Of these, 4 give a SOC of length 2; 6 give a SOC of length 3; and 6 give a SOC of length 4. The answer is therefore (4*2 + 6*3 + 6*4) / 16 = 3.125.

  3. "**a*cd"

    "cde***"

    "abcdefghijklmnopqrstuvwxyz"

    Returns: 10.0

    It makes no difference what the unknown characters are; the SOC is always the same length.

  4. "h*phz*"

    "hzph*p"

    "zph"

    Returns: 10.555555555555557

  5. "a*a*a*a*a*a*"

    "*a*a*a*a*a*a"

    "abcdef"

    Returns: 23.6983063804134

  6. "********************************"

    "********************************"

    "abcdefghijklmnopqrstuvwxyz"

    Returns: 63.958459262501435

  7. "********************************"

    "********************************"

    "yz"

    Returns: 62.358835095751274

  8. "ngafkhcmriluvssts*qbpoxzdwjsstss"

    "sstssq*poxzdwjsstssyeng*fkhcmril"

    "ngafkhcmriluvqbpoxzdwjtsye"

    Returns: 58.9792899408284

  9. "vnmzifxyrokbdbdbdwejgpuqhabdbdbd"

    "bdbdbdwejgpuqhabdbdbdcsltvnmzif*"

    "vnmzifxyrokwejgpuqhabdcslt"

    Returns: 43.0

  10. "hkizsb*fdtnlx*orefdtnlxqoref*tnl"

    "fdtnlxqorefdtnlxq*refdtnlvpaucjm"

    "hkizsbgxqorefdtnlvpaucjmwy"

    Returns: 63.42250796540738

  11. "devss*grws*sgrw*ssss*rwsssgrwsss"

    "sssgrws*sgrwsssssgrwss*grwsssliu"

    "devgrwsliuknypxfcamzjbqtoh"

    Returns: 60.7603528801326

  12. "qffflfffdffflfffoffflfffdffflfff"

    "ffflfffdffflfff*f*flfffdf*flfffb"

    "qodlfbwzrxgmvjiuakhcespytn"

    Returns: 48.999089667728725

  13. "gwftstitstybzj**k*rxlhnoatstitst"

    "tstitstybzjcukerxlhnoatstitstpvq"

    "gwfybzjcukerxlhnoaistpvqmd"

    Returns: 56.998748293126994

  14. "g*yxhkarjd**eo*wsqzb**tzb*z*zb*z"

    "zbuztzbuztzb*ziflmgnyxhkarj**ve*"

    "gnyxhkarjdpveocwsqtbuziflm"

    Returns: 62.88432983752826

  15. "**ypj*dvxrt*ekmg**ypjqdv*r*ae*m*"

    "bcy*jqdvxrtaekmgbc*pjqdvxrtaekmg"

    "bcypjqdvxrtaekmgihnwzolfus"

    Returns: 63.96153845954638

  16. "wookajoomookaj**mook*joomookaj**"

    "oo**j*omo*kajoomookajoomook*j*oy"

    "wmkajoyvihbeutlqngfdpszcxr"

    Returns: 63.960046084412085

  17. "wccc*cccc*iccc*hk*nccc**cccciccc"

    "cc*icc*ccicccuhkg**cc*ccc****ccd"

    "wuhkgnicdyzfrxevqbaolstmjp"

    Returns: 61.95560817198278

  18. "b***rcqldx*k*u*uvuvumhwpvuvu*uvu"

    "*uvuvuvumh**v*vuvuvu**fz*enybsij"

    "bsijrcqldxakmhwpvutofzgeny"

    Returns: 63.729289877206384

  19. "k**l**e***edbdedtrmcp*ed*d**bded"

    "dedbdedbd*dtrmcpdedb*e*bdedyj*a*"

    "khvlqtrmcpbedyjiafxogzswun"

    Returns: 60.99408250357518

  20. "drc*drchdrch*rapbndrch*rc*d***d*"

    "drchdrch*rchdrapbn*rchd**hdrc*dr"

    "apbnchdrgiekqujtwyflozvxsm"

    Returns: 63.88460663042443

  21. "gzmdiftpy***aop*kpn*rpykp*aop**p"

    "*ykpvaop*k*n*r**kp*a**ykpcjeus**"

    "gzmdiftnqrvaoykpcjeusblhwx"

    Returns: 63.96136694229562

  22. "qkt*n*a**am*ma*ma*aama*aa****ama"

    "amaa*ama*mam*amam*amama**a**srxz"

    "qktcnemahusrxzwfdjyolvgbpi"

    Returns: 60.99998246678082

  23. "e*cjxuay*gfggfgqgf*gf*g*gqg*ggf*"

    "gfggfg*gfgg*gg*gqgf*gf*dhow*sbzl"

    "evcjxuaymqfgdhownsbzlkritp"

    Returns: 63.88017749202402

  24. "ez*jc*ybn**rxvsqgo*ah*itpl**dezd"

    "ezdez*jckyb**f*x*s**owahuitpl**d"

    "ezdjckybnmfrxvsqgowahuitpl"

    Returns: 60.99982931269914

  25. "e*stn**oo*chy*mb*g***ch*xmblgo*o"

    "o*oc*yxmb**ooochyx*b*g*oopwdjfar"

    "eustniqchyxmblgopwdjfarkzv"

    Returns: 62.923076923015046

  26. "b*o*j***w**n*ribi*fe*z*h**t*d*b*"

    "*bis*e***hk*t*d**ioujpxcw*m*l*sf"

    "bioujpxcwamnlrsfeqzvhkgtyd"

    Returns: 63.95567819754211

  27. "*ll*c*ll*cl**iq*n**lllt*l**t*l*l"

    "lllt*ll*t**l**q*nogllltcll**c*ll"

    "iqknogtclhrvwasufmpbejyzxd"

    Returns: 62.92307650100612

  28. "dq**m*cy*f**q*q*bvqq***cya**x*q*"

    "qqq*jc*af*xq*qkb***qm**y*f*xqq**"

    "dkbvmjcyafuxqzgphowrtsilne"

    Returns: 63.92159763313407

  29. "*y*susi*cv**sr****lbo***si*cvs*s"

    "*usi***s*sr*w*n***d*us*k*vs*s**t"

    "hyfrgwxnlbodikcvusaztqmjpe"

    Returns: 63.958579849419614

  30. "*n*o*eg**w**fvd***l**km***gspw*e"

    "*e*spw**fvdj**l**k**e********hr*"

    "qniofvdjyalbtkmcgspweuhrxz"

    Returns: 63.885923323519535

  31. "*n*iazp**k****q**tvey*cxh**gng**"

    "g*g****z*jdk*****bftve******mn**"

    "mngiazpjdklworqbftveyucxhs"

    Returns: 63.955453116918136

  32. "*nx*g*ae*****rm*il*u**f****tza*t"

    "zaetz*e***si*yu*cfdza*tzae*bk*pq"

    "vnxhgrmsilyuwcfdzaetbkjpqo"

    Returns: 63.84615383320533

  33. "*g*eh**gae*s*gayc***ehs**a*h***a"

    "qga**sqg*eh**g*ycqgaeh*q***hsq**"

    "ycehsqgauxrvzwnpbtmflijdok"

    Returns: 63.99555337695387

  34. "*r*z*u**kaaev**i****j*oa*evf*iaa"

    "*a*vfbi*a****o*a**f*********m**p"

    "grpzyutxkhcjsoevfbiaqdlwnm"

    Returns: 63.91863846409709

  35. "hcm*k*i****k******gmd***z*m*kfi*"

    "***fi*bmd********m***iz**d*fi*r*"

    "hcejpgbmdkfizrlaswonuvtxyq"

    Returns: 63.95844647959968

  36. "wrssss*****s*s*g**kss****as**sss"

    "*ss****s*sss****k*****sass****nj"

    "wrgulkasnjqbpcdiyxhefzvtmo"

    Returns: 63.87885828137078

  37. "yfvko****rg*****mq*m*m*r**n*m***"

    "****rg**lm**q****qr***lmqm****zb"

    "yfvkoxrgunlmqjhezbwpdatics"

    Returns: 63.95845926216251

  38. "*ip*w*np**jhf*****qbxv**ygksm***"

    "****h*ar*******t*****m******o*h*"

    "miplwcnojhfarezdqbxvtuygks"

    Returns: 63.95845925903515

  39. "*i***m**ja***ur**y***b**km*****d"

    "**x*an*qu*e***s***h******n**vip*"

    "vipofqurewyzstbghkmcxjandl"

    Returns: 63.95862811399691

  40. "**k**fno**cno*x****x****x***ix*n"

    "no*xc*o****o****oix***ix**z*hs*p"

    "rwkgefoixcnzlhstpaubqmvjdy"

    Returns: 62.99999957917325

  41. "***e****a******o*****oi****p**o*"

    "***i*dk******f***oi*******ool***"

    "xqgefwiadktpzoljmcruvnbhsy"

    Returns: 63.95845968073172

  42. "ktfdc*ag*****l*********w*k******"

    "*t*****dcp*g******vi*********o*t"

    "ktfdcpagnezrylviuxbjsmhwqo"

    Returns: 63.958459262539606

  43. "**e*****o**l*****b**a****w*s***x"

    "*****q*****k*n***********f****x*"

    "fsevpxqzocmlkunhtbdragjyiw"

    Returns: 63.95845927854264

  44. "********a**tp**y*********tp***h*"

    "y***d**b******y******b***q*****z"

    "rkwxdaebtpgqhyfoznuclismjv"

    Returns: 63.96136087264176

  45. "*nk*****k**n*q********k*b***k***"

    "***qb***kq****bn******k*b****q*n"

    "kqbnreihmlpfxzcgyjatowvsud"

    Returns: 63.95845917898664

  46. "**w***hs*kz***i*******tq****n*y*"

    "*******s*****u*g***m**t*********"

    "sckzrduigaefmbltqxvownjyhp"

    Returns: 63.95845925602398

  47. "zyze****z*****xm*******z***ds***"

    "**z*******t*h************z***z*z"

    "ktvhcxmlinpbqfedsyzojraugw"

    Returns: 63.958459276176946

  48. "**r*********s****vhqi********o**"

    "*s**s**s***av******s******s***j*"

    "tnrkuywavhqiclosfdpjgzbmxe"

    Returns: 63.95846784786314

  49. "******p***p*p***************p***"

    "q**p***pq****p******************"

    "wojpqtianklbmxugcvedhzsyfr"

    Returns: 63.95846790339221

  50. "*******i********vev*******v*****"

    "*************v****e*****j*w*xs*c"

    "ormpuayidtvekjbwlxsqcnzhgf"

    Returns: 63.958459262501435

  51. "**ztp************o**************"

    "*********************s********z*"

    "fdelwomgprhuxsztncyajkbqvi"

    Returns: 63.958459262501435

  52. "w********v******************q***"

    "**************q*q********e****bp"

    "wfzhxmsajviygqutdnoerclkbp"

    Returns: 63.958459262501435

  53. "*************n************v*****"

    "***************v**t*******v*****"

    "ilowjtzngayvpxfbeurkmscqhd"

    Returns: 63.958459262501435

  54. "*********l**************v****l**"

    "********************************"

    "guoxvpltrisamjfwekcdnqbhzy"

    Returns: 63.95845926250143

  55. "***k********************w****i**"

    "***********w********s***********"

    "amgkvyohferqptuncbwdjixszl"

    Returns: 63.95845926250143

  56. "********************************"

    "********************************"

    "gtybjmculkwqivodeashfxnzpr"

    Returns: 63.958459262501435

  57. "********************************"

    "******************t***k*****i***"

    "caltjfrkndobziywesxgpuqvhm"

    Returns: 63.958459262501435

  58. "********************************"

    "********************************"

    "a"

    Returns: 32.0

  59. "rvvvyxdvvvgtvvvyxdvvvgtvvvyxdvvv"

    "vvvyxdvvvgtvvvyxdvvvgtvvvyxdvvvl"

    "ryxdvgtl"

    Returns: 33.0

  60. "y*whsejcccoqpidccclkmcccoqpidccc"

    "cccoqpidccclkmcccoqpidcccaurnfgt"

    "yxwhsejoqpidclkmaurnfgt"

    Returns: 39.0

  61. "ydawbtelawbtelpvkongawbt*lawbtel"

    "awbtelawbtelpvkongawbtelawbtel*q"

    "ydawbtelpvkongcq"

    Returns: 56.5

  62. "yoyyoyoyyoyoy*oyyoyyoyoyyo*oyyoy"

    "yoyyoyoyyoyoyyoyyoyyo*oyyoyoyyoy"

    "oy"

    Returns: 52.5

  63. "ywxvpjela*elujelajelajelujelajel"

    "*el*je*ujelajelajelujelajelhrnbd"

    "ywxvpujelahrnbd"

    Returns: 63.72954074074074

  64. "xygsgsgsicvugsgsgsgsgsicvugsgsgs"

    "gsgsgsicvugsgsgsgsgsicvugsgsgstf"

    "xyicvugstf"

    Returns: 34.0

  65. "gyxfffwvbjpfffto*hiunfffwvbjpfff"

    "fffwvbjpffftolhiunfffwvbjpfffdmr"

    "gyxwvbjpftolhiundmr"

    Returns: 52.05263157894738

  66. "xygrp*fqkicnlokikicnlokikicnloki"

    "kicnlokiki*nlokikicnlokiabdejstu"

    "xygrpmfqcnlokiabdejstu"

    Returns: 55.27272727272727

  67. "iyuwtibmhnqpjaedfkcrosglvxiyuwti"

    "iyuwtibmh*qpjaedfk*rosg*vxiyuwti"

    "yuwtibmhnqpjaedfkcrosglvx"

    Returns: 57.998336

  68. "ywafsucttqttttqttilrdkttqttttq*t"

    "ttqttttqttilrdkttqttttqttmx*bno*"

    "ywafsucqtilrdkmxjbnoh"

    Returns: 61.857142857142854

  69. "rytxmvrrytxm*rqocdryt*mvrrytxmvr"

    "rytx*vrryt*mvrqocdrytxmvrrytxmvr"

    "ytxmvrqocd"

    Returns: 62.391200000000005

  70. "jyxhskpgmmrcmmovlmmrcmmovl*mrcmm"

    "mmrcmmovlmmr*mmo*lmm*cmmqd*i*btf"

    "jyxhskpgrcmovlqdeinbtf"

    Returns: 61.79954835735265

  71. "*uuguu*myvu*ugu*uugu*umyvuuuguuu"

    "uuu*uuumyvuuuguuu*guuumyvuuuguuu"

    "myvgu"

    Returns: 60.119808000000006

  72. "yq*vsejm*ocrrrr*drrrrrrrrrdrrrrr"

    "rrr*rdrrrrrr*rrdrrrr*ipnbaglktuw"

    "yqxvsejmfocdripnbaglktuw"

    Returns: 60.66663652584876

  73. "ywxdu*auiauiafrglh*vp**uiauiau*a"

    "*iau*auiaf*glhjvpqcui*uiauiasokm"

    "ywxduiafrglhjvpqcsokm"

    Returns: 63.931972789091716

  74. "xyr*jtpscc***ccc*flccoflcccof*cc"

    "ccoflc*cof*ccoflccco*lcckdbig*nq"

    "xyrajtpscoflkdbigmnq"

    Returns: 61.96062499957031

  75. "xblikg*vublikge*mp*blikgyvublikg"

    "blikgyvub*ikge*mpdb*ikgyv*b*i*gq"

    "xyvublikgejmpdq"

    Returns: 58.46666665964335

  76. "yvxb*anj*jgfphnjnjdc*jnj***hn*nj"

    "njnjg*ph**n*dcnjnjgfphnjnj*lkimt"

    "yvxbuagfphnjdcelkimt"

    Returns: 61.899999992264256

  77. "u*vwlhfg*e**okmcptet*t*okmcptete"

    "t*te*kmcptetet**kmcptetea**dbsr*"

    "uyvwlhfgokmcpteaindbsrj"

    Returns: 63.825032786224774

  78. "y**luqom**mmrmmrmmadc*mrmmr*mrmm"

    "mmr*mrmmr*m*d*mmrmmrm*rmmjehk**p"

    "yvxluqormadcjehkinp"

    Returns: 61.68418750619122

  79. "*ssss*s*sytss**ssssssytsssssssss"

    "s*ss**ss*ytsss*s*ssssyt*ss*ss*ss"

    "yts"

    Returns: 61.75791772850713

  80. "y*xtdha*m**q*qsqm**q*qmq*qmqmqmq"

    "qmqm*mqsqm*mqmq*qsq*qmq**ogpelc*"

    "ywxtdhasqmogpelcn"

    Returns: 60.7647055509194

  81. "xydp*h**pupvhtspokf*vhts*upvh*sp"

    "pv**sp*pvh*sp*kfpvhtspupvh*s*ai*"

    "xyduvhtspokfain"

    Returns: 62.977776753540475

  82. "y*fwafwachgena*w**wac*gena*wafwa"

    "a*waf****g*n**wafwac*gen*fwa*w*b"

    "yfwachgenb"

    Returns: 62.694299998287

  83. "xhqy*v***qnlrfajbmp*ds**qyivkghq"

    "h*y*vkghq*lrf*j*mp*d*ohqyivk*h*t"

    "xyivkghqnlrfajbmpcdsot"

    Returns: 63.908433508640115

  84. "baxwe*q*pm*eeq*pm*eqdpm*ee*dpm*e"

    "eeqd**e**qd*meeqd**eeeqdpm*ech*o"

    "baxweqdpmchuo"

    Returns: 62.92306076267237

  85. "mybuiuituiuis*r**fng*h*uiu**ui**"

    "u*ui*u*uisl*q**ngjhou*uit*iui*p*"

    "mybtuislrqkfngjhoapd"

    Returns: 63.94484368750001

  86. "xhhywr**kpl*ohhs*mhh*w*d*kplf*hh"

    "hh*w*du****ohhsgmhhywrd**p*fo**n"

    "xywrdukplfohsgmn"

    Returns: 61.99609374720603

  87. "ysa*jt**oidt*toidt*t*i*tu*oid*ut"

    "t*to*dtu*oid*u*o**tutoi*tu*ecn*r"

    "ysavjutoidecnxr"

    Returns: 62.99110312799795

  88. "*xvxvxvxvxvx***pi*x**vxv*vx*xv*v"

    "xv*v*v*vx*xvxv*imx*xvx*x**v*vxvh"

    "yxvpimh"

    Returns: 63.167253276764086

  89. "qvq**v**myq*qv*v*v*v*v***vqvqvqv"

    "qvqvqvqvmyq*qvq*q*qvq*myqvq**vq*"

    "myqv"

    Returns: 57.49999046294397

  90. "*eparrb*dkljiv*h*r*r*u***ji**h*r"

    "*rbudkl*iv*h*rrr*u*kl*ivmhrro*fq"

    "yepabudkljivmhronfq"

    Returns: 63.84487534621749

  91. "y*s*c**f*fo*tc*cf***fcfogtcfcfcf"

    "cf**c*o*tcf*f*f*f*fogt*fcf*fl***"

    "yxsuogtcflmpj"

    Returns: 61.98725533264266

  92. "yw***f**acaa***a*aa***a*caaaacaa"

    "***a*aac*aaacaaaac*aaacaad*mqg*n"

    "ywvetfrcadpmqgsn"

    Returns: 63.93199844275758

  93. "uyxvj**m*na*n**nnafnn****q*naf*n"

    "n*afnn**n*fn*afnnq***fn**h*to***"

    "uyxvjdcmqnafehbtoklr"

    Returns: 62.99699999999894

  94. "y*x***ir**hg**m*q*r**h*o*me*i*j*"

    "qi**lhgokm**irj*hgok*eq*rjl***dp"

    "yaxtvqirjlhgokmefbudp"

    Returns: 63.95235524292766

  95. "*yx**wij**eqk*ee*e***hee*e*qkhee"

    "*****eeae***h*eaee**heenb*lfod*p"

    "tyxsvwijgqkheanbmlfodrp"

    Returns: 63.95436788980238

  96. "*qt*waewa*w*h*fk*gl*p*ojew*e*a*w"

    "*waew*e**hc***gl***oj****wa***d*"

    "yqtaewmhcfknglipvojrdu"

    Returns: 63.86542070982879

  97. "ywt***jptu**tjpt*ptjptu*v*j*t*pt"

    "t*ptj**u*v*j**j*tjp**cvtj**j****"

    "ywucvtjpqb"

    Returns: 62.699996984303

  98. "**e*d*m**nlkn*pk****kn*k*qp*n**n"

    "k*l*n*pkn***knlknqp*n*knji**yf**"

    "axewdbmcqplknjigvyfsr"

    Returns: 63.995439632844246

  99. "**v**r**c***c*v*un**c*v**r*****v"

    "vvc*vv*r**crvv**vvcrvvcrv**rvv*p"

    "ybcrvunep"

    Returns: 62.887771146837395

  100. "w*xlpb*d**d*d*ddd***od*dd**dd*d*"

    "***dd****ddgqod*ddddd*d*dise*c*h"

    "wyxlpbmdgqoiseackh"

    Returns: 63.937880110937336

  101. "y***jfq**l*q*fqqhnqqjfqq**q*j*q*"

    "*q**q****q*fq**nqq******qqj*q**p"

    "ywvljfqhnop"

    Returns: 63.87654577886677

  102. "axvbud*fmi***imi***i*ikpmi*i**mi"

    "mikpmi**k**im****imi**mi*g*lncyo"

    "axvbudhfkpmirgjlncyo"

    Returns: 61.99949984390624

  103. "t*nokn*g*h**nok*efno*nw***i*nokn"

    "*ok****h*j*ok****o**wgahi**o****"

    "tbwgahijoknefmr"

    Returns: 63.91999999999885

  104. "******ok*q**li*i**i*a*j***iiilii"

    "ii*i**li*****i**ii*li*cdh**b*usz"

    "yxwvrfokpqlimagjcdhtnbeusz"

    Returns: 61.99556210789113

  105. "y**hgb*ga*o**ng***gb*gal*q*ng*e*"

    "**e*a****ngb*ggb*galoqrn*b***m**"

    "yvuhaloqrnbegfmid"

    Returns: 63.933067203241265

  106. "yx*f*s**iik*lm*gdwi*ike*mngdwi**"

    "**ik**mngd***i**l**g*wi*****zjtp"

    "yxcfrsbikelmngdwohqzjtp"

    Returns: 63.95263039880545

  107. "**uuu*uv**aorf*hlj********eu*uu*"

    "u**uuv**a***nhljib*p**d**u*uu**x"

    "ymuvqtaorfnhljibkpcgdsewx"

    Returns: 63.87667712000001

  108. "****xxw*xxxxx*v*x**wv*xxx***x***"

    "***x*v*xx**wvx*xxwv*x*xxwv*x*xb*"

    "syxwvba"

    Returns: 63.809344900409386

  109. "*xx*xxx*y*c*fb*rl*******xx***xxx"

    "x*x**xx*yw*ufb**lot*a**mxx***xxx"

    "xywcufbqrlotjahkm"

    Returns: 62.882026447456006

  110. "y*u**s**licf******k**k*f**fknfkn"

    "f***knfk**k*fk****fkn**oqjb***hx"

    "ywuerstmlicfkndgoqjbapvhx"

    Returns: 63.99498498457279

  111. "ywvxu*****tb*p*l*ag*n***v*******"

    "**u*v*uv*b*p*liag*n*sm*x*v*x***o"

    "ywxuvtbqpeliaghnfsmko"

    Returns: 63.94761364802748

  112. "*x*g******a**aal**c**a*v**va**aa"

    "aav*****vaa*p*cb*aavaav****a**d*"

    "yxwgvalphcbftodn"

    Returns: 61.999954167793476

  113. "****db*clp*eg*********egrt*b**l*"

    "b***pmeg***bu***m*gr*hbu*l*o****"

    "yawndbuclpmegrthoqiks"

    Returns: 63.95201612300969

  114. "******"

    "x***x*"

    "hx"

    Returns: 10.48828125

  115. "da"

    "**"

    "tvazgdrm"

    Returns: 3.84375

  116. "*v***"

    "*v***"

    "kqv"

    Returns: 9.289894833104709

  117. "hjjjjhjhj"

    "jjjjhjhjj"

    "jh"

    Returns: 10.0

  118. "******"

    "******"

    "oty"

    Returns: 11.31881431805224

  119. "o"

    "o"

    "o"

    Returns: 1.0

  120. "****i"

    "*****"

    "zxi"

    Returns: 9.326169791190367

  121. "y"

    "y"

    "y"

    Returns: 1.0

  122. "*rrrr**rr"

    "rr*r*r*rr"

    "r"

    Returns: 9.0

  123. "emn*p"

    "udmae"

    "kpngdwiouezfxjtbarmy"

    Returns: 10.0

  124. "*xtj*"

    "**r**"

    "jrxt"

    Returns: 9.59375

  125. "f*f*f*ff"

    "f**fffff"

    "f"

    Returns: 8.0

  126. "t****c**f"

    "*uu*uu**u"

    "feticuk"

    Returns: 17.855468558238176

  127. "v*z****a"

    "h**a*z**"

    "ivzhap"

    Returns: 15.911626526539402

  128. "*"

    "l"

    "ydjwlf"

    Returns: 1.8333333333333335

  129. "**"

    "*s"

    "s"

    Returns: 2.0

  130. "zzz"

    "zzz"

    "z"

    Returns: 3.0

  131. "f"

    "r"

    "karyhpjf"

    Returns: 2.0

  132. "ypyypypypp"

    "yppyyypyyy"

    "py"

    Returns: 17.0

  133. "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a"

    "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a"

    "abcdefg"

    Returns: 60.61807296755505

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: