Statistics

Problem Statement for "KDoubleSubstrings"

Problem Statement

A k-double string is a non-empty string consisting of two equal length halves, where the first half differs from the second half at no more than k positions. For example, "contestcontest", "oopoop" and "aa" are 0-double strings. "contestkontest" is a 1-double string, and "poorpork", "artbat", and "yesyep" are 2-double strings. Obviously, all 0-double strings are also 1-double strings, all 1-double strings are also 2-double strings, etc.

You will be given a String[] str and an int k. Concatenate the elements of str to form one long string, and return the number of k-double substrings contained in that string.

If the same string exists in several different positions, count it as many times as it exists. Also, k-double substrings can overlap. See the examples for more details.

Definition

Class:
KDoubleSubstrings
Method:
howMuch
Parameters:
String[], int
Returns:
int
Method signature:
int howMuch(String[] str, int k)
(be sure your method is public)

Constraints

  • str will contain between 1 and 5 elements, inclusive.
  • Each element of str will contain between 1 and 50 characters, inclusive.
  • Each element of str will contain only lowercase letters ('a'-'z').
  • k will be between 0 and 100, inclusive.

Examples

  1. {"aa"}

    0

    Returns: 1

    "aa" is the only 0-double substring.

  2. {"aaaa"}

    0

    Returns: 4

    There are four substrings of even length and all of them are 0-double strings.

  3. {"contest", "kontest"}

    1

    Returns: 14

    Each pair of consecutive letters form a 1-double substring and the whole string form one more 1-double substring.

  4. {"abacaba", "d", "abacaba"}

    1

    Returns: 34

  5. {"areyouready"}

    2

    Returns: 18

  6. {"a"}

    1

    Returns: 0

  7. {"aa"}

    2

    Returns: 1

  8. {"aaa"}

    3

    Returns: 2

  9. {"aab"}

    4

    Returns: 2

  10. {"cabb"}

    5

    Returns: 4

  11. {"cbbb"}

    6

    Returns: 4

  12. {"aad"}

    7

    Returns: 2

  13. {"aabbdc"}

    8

    Returns: 9

  14. {"dbe"}

    9

    Returns: 2

  15. {"bb"}

    10

    Returns: 1

  16. {"efd","c"}

    12

    Returns: 4

  17. {"edeebaefdcc","aag"}

    0

    Returns: 3

  18. {"dcabeccabafg","fafhe"}

    16

    Returns: 72

  19. {"ihcgcifgba","hbicgfhgehdiadd"}

    18

    Returns: 156

  20. {"agbehdid","eahdbbc"}

    20

    Returns: 56

  21. {"icckfifbjkkdiihkgeab","kbabbjdhdjdecahachkkc","habeegkjhdbh"}

    22

    Returns: 696

  22. {"aeebceilcdb","gidijbiadcce","eiblaafaegea"}

    24

    Returns: 306

  23. {"bkfddfelgdelekmjjmllaeam","lchfkkaa","jffefhilmhihgffjdgh"}

    26

    Returns: 650

  24. {"ehckhedh","bdncndjki","dajaedhmhkncelkdcc"}

    0

    Returns: 1

  25. {"oeicbknnlbkcdcladjehjlomfc","jhehoiglh","mlllfnbbihde"}

    30

    Returns: 552

  26. {"c","ndl","npnfkllnmieoknfibcnbbij","mjdkjbhnjhgkggjknj"}

    32

    Returns: 506

  27. {"hlhnbbcamjmmqfboiopcagqqlkbdqkmlcg","kependmnonipqogjnkqicli","imkkohqfhigc","ldgjnnbhnmmmmqnlqp"}

    34

    Returns: 1841

  28. {"ofckocgmhcjjclffokm","aaomqeccemrbrp","nhaqrjaolqlfbngepbgoinigrerremplckr","jahfa"}

    36

    Returns: 1332

  29. {"gablkobidpnlmpfg","raldoeojcisihkpkdpqhfpaoggqpcilgjiqap","khkaeskdlljks","b"}

    38

    Returns: 1122

  30. {"gielldmtgoona","tttfjttrslotcrprmccinsbk","ddpenjimco","joblodkpaqgcreqljomkbmatoecpkt"}

    40

    Returns: 1482

  31. {"bbcokbapkekmgjsnppaqrgoiatjdmmhhpggtcraq","aebtkq","ooasjbgpsgjkcl","nfgiliudabtnklftbsstthujunmhcmrrtglr","outpqhkjefchoggfbakinnbtjot"}

    42

    Returns: 3497

  32. {"bnkoimragqabgvndq","ilfltjjjduogbrucejgqvptffpnrbqmdhqfehbrva","vnkdsaeiisqtkalnaulig","elcnnfpovstpljgur","tnmiudeqboqtjjofmj"}

    44

    Returns: 3114

  33. {"saqwddmppwwwaheujifkjvmqdawuedhbcs","gsbljhudsgunbmmjlsqdvvekfhbvijo","hhvamfknehd","wklvielfldrpdbovgujmdbgrbgmbupgfkkpgpvavhvd","ubutvpcuhtnrrlhasuoetfjqki"}

    46

    Returns: 4681

  34. {"ractorelmrugqwmisah","cflimcmk","nscjeuudjoutnogivvajoqbojowpduboluwp","veqptmtopcaarnhfruevwgdkgothmkpih","pxocnqcftcmeldgcgogonduuwemrgihhnguaixu"}

    48

    Returns: 4267

  35. {"edjpnovxcvsbpkelvocwvxxvvnnnbvdmmyowfebt","akcpadvqcn","xtgennm","yjjpstekoytxkjyiwptrufibpnsadrcjiepyahuc","wrsohefbjblwrwbalekvxoayujcnhjoijqx"}

    50

    Returns: 4156

  36. {"ufbxjfzjymmrwneystelujapvdtabfwgumcrtiqztldoig","njncgxnbdpmefbmxbahhapunciecjokesttzepkrvaoqnt","ubyfkdtryifvjzjbfcxedjsytupnnkdtgwbudpvzqgbwhy","cdbilywllahbclgxwaeipoeqowjymkfewxagtibizbsmjy","bjlugtwsigpkejttlbiecrsmbcqfnzpxkeolejpebfgnux"}

    7

    Returns: 1613

  37. {"ufbxjfzjymmrwneystelujapvdtabfwgumcrtiqztldoig","njncgxnbdpmefbmxbahhapunciecjokesttzepkrvaoqnt","ubyfkdtryifvjzjbfcxedjsytupnnkdtgwbudpvzqgbwhy","cdbilywllahbclgxwaeipoeqowjymkfewxagtibizbsmjy","bjlugtwsigpkejttlbiecrsmbcqfnzpxkeolejpebfgnux"}

    92

    Returns: 12852

  38. {"unuzipwtfmvdyxwahaanpjvlrtizdwazemsazbueziptrgc","vmwdmrhckvetgowivnogroqoavngdpzwpahcjjpyfhdbmhm","obuqtvrojcnnwsijmvvkqlhitgcbftdgimrossihfiphmto","rmvfosamsqendwvfgbfpdypkomvczinndhnmjcdeuvogyeh","cpvfhrzrtcaijjiunqaavzgleciuaswdgfumpvbahtqfjux"}

    8

    Returns: 1934

  39. {"nycpcydapxqcuenjxfwpvaqcjmhpeujyrxhluahxlldpukk","qayfyhtebvmlvghjudnqleuqfjxnzgbsffpiiuspnhtnadm","ixlpxgeakylpeotuszkgbzdxbxfbsbquvyucdcgggpairzy","eybbiofzvmnjopuucztuxunyvqpxrtdfebnvmmiclpuyquu","yppejanwmsrwyywlahuezxbbxcseoopkyituuffisbjuuzr"}

    94

    Returns: 13418

  40. {"ngvrbiakxxblxngmnmsrqylxdcxqelprzxxuduneshpwclxw","bsboobdtgmacigpoluxlyyaxykknjuubmzhcqqstagbsqcja","uewkygqgsdqfydhrchxmrnerwrrzpcfqgcyuxhmbisxnjtpy","kjxcemahqvpnvblmdjegznqaukgtqbpuiopkptzigooqnsnn","hlxdbjxnwewbjectvurhofkahzyazcychyywfubetxstgdjc"}

    9

    Returns: 2165

  41. {"eeyqmfoimuxdijmhrqruwlswvgvjspypzzcaectnpybgjlfs","xvdvzslbbmyvgerprwvxesucsmckvtznratcmudisxhlflyp","nqjovufgpmvtamrvcpvkeiazvbvubxubaokujrdjopkyizoc","oboooluwsljhnplzpnvdppqjsvhaqncjhisuqwueftmbenbl","eozzftccyymatayldatuviicsbdzmflksabtefjqodcrjlpj"}

    96

    Returns: 13986

  42. {"emtslpkrtugokrfjgxowojntrylkvgdiizsjmvzvvumnrltzk","pxmgzltkoocidykzdbxaveujzyzyodjykptirgqlmvbrbvhpx","itoylmtajidvdnsprxryfrmrwryhctnpfmypivuyrorbzdkwe","otciqzrhcooxqyafvpervopvqbkqqsjywdedrnqhxkhxhudag","tkiqwfopdygzxvjamlaaknjrozstfsuhrybzncckrshochpbe"}

    10

    Returns: 2471

  43. {"drmmmospzreibqcbnczpimzghankqglbjxugqqiycedvsleaa","fkopdmnhjvhehczdihvnnysmojhoesuckyqtaxvdwdahbhfau","jhjhvvfkslsvqkvoaladsknsvxgedpxqpiasslzzxspvvbrww","odesjiwjupqmmumbrlkpmaijrstzvkfksrgbaqwyjsxhojksf","bmmubklsbfhfnfkiqaxhicotksasqrpqdoyyrhzcuvhdhgfqq"}

    98

    Returns: 14595

  44. {"xvqwrnbzqfrdyawiuodbomappqupksiivlskejslcgdsvcifia","viqvxbljbncbjoakxhtdlouqbgwgdsqegkeqbsojorqbdoeomn","etstzkldtgtsvpkekvqznrwyvjbijclkxdrgdmgrsgbfatphrn","lcgncdqjoufaswhlieemkszggmhoxdugmiqtctlwtnoplxkxbk","krctslmaieckqdaslccjuimogbaikyudlfkfbjiujcntmjiybs"}

    1

    Returns: 271

  45. {"xiesqvfhbfwhrjoeoblxanjzzhoohjxuejkqpxiwpnhhfdgoly","ecfiynsgybacvykyieczneoqgbpuvccolzivvfagmhttmgmxko","ugjgpikynpsgnorghrhmfkvcaqkuibszqegiovrmybgdfbjpsc","lptycrpjpjkbzkdghhmzmjbmcyklpbvqtebwnzzgzqptpewtsu","neamxovvsjuakvpxadndrvavetohikjkohhqmuzoltxnlqvqrb"}

    100

    Returns: 15179

  46. {"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

    0

    Returns: 15625

  47. {"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

    100

    Returns: 15625

  48. {"abbbaaabaaaabbbaaabababbbbbaabbaabbbaaaaaaaabbbbba","bbaaabbbabaabbbbbababbbbaabbaaabbbababaabababbbabb","baaababababaabaabaabaaababaabbbaaaaaabbaabbbaaabba","aaabbaabbbbabababbaabbabbabbbaababbbbaaababaabbbaa","bbababababbabaaaaaabbaababaabbabbaaaaababbabbabbbb"}

    0

    Returns: 235

  49. {"ddacbdddbbdddccaabcaaddaadaaddabdbabbbddaaadcdcdca","cbdabacbdbcaacbdaaddcdccbbaacaaccabbbdcdabadabcdab","aaabdbbdacbdcccdbdabdcabbcbdcbcbcddaaadbacbdbbdbdb","abcadbdaabbddcabccccaccddaacacadabcdcbbcbbcdabdbcc","dbcabbcdccbbabbcddcbbbcbcaabdcdbcbcdabdbacbddccddc"}

    100

    Returns: 15624

  50. {"fhehddgfgfbfadadfceaadhcaaeecebafghfdfcegcgcdhddhf","ebgaefefgghgcdahdcfhgafcahbgghgagefddeahdhchdadeae","dfahffgfebaggecdhcedgehgedchfhdhgedebfbaddgfdabhce","dbdcbeehgcfeehbfbebadfccdhfaghhghaggbgehhefffchaaa","hehdeeebhehgeaehdgbbhcbecfgacgfffbabbffdbgffhdbebf"}

    100

    Returns: 15467

  51. {"adfjpljckiajabmiecdokegnkafclinfcflkgpdggcbfgficfb","cpmiffehmcdbgkkpkoecnlhfmgfibfdlgdedamnhonbepimgbf","gledbcjdhfndjnlfcmnilmgmldhpdhkkbpopphkolbgofajdbm","ikababdcbfjojebfpcjoobikopmbabonpekdpognogehnmkcon","aombgfhbipkjkchebaokaiidglhiahhoopnkomgjmbmghfgocc"}

    100

    Returns: 15274

  52. {"buqfgbuzwwwjrxpouplspmwgcrvitjklxespkhhfnabeweqicf","tvkrbguozzadrwfehyyetlbwxebbsdpeydectydazzvjpylrfv","dksypsrlexdbhrmlpdvfrbgyewkytqsisiqmgvuoutsmvcwxxc","uwmuhuvlaylajawtjemhrgvjxaxnvnhysjhcdpdnxhwarosjho","fdgdnaonjprftvwvbajrxtkqbmxmcplomwlgkjxbtwyqwkcerw"}

    100

    Returns: 15184

  53. {"abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab", "bcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcaba", "cabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabca", "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab", "bcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcaba" }

    1

    Returns: 1540

  54. {"aaaaaaabbbbbb", "fffffhhhhbbbbccc", "aa" }

    3

    Returns: 97

  55. {"asdf", "dfghfgh", "jghjghjfhksdfgsd", "sdfgsdfgsdfg", "sdfsdf" }

    2

    Returns: 132

  56. {"abcdefghijklmnopqrstuwxyz" }

    7

    Returns: 126

  57. {"aa" }

    5

    Returns: 1

  58. {"areyouready" }

    2

    Returns: 18

  59. {"aagsdfhhhhdgfgggggdfdgdfffff" }

    1

    Returns: 49

  60. {"aa" }

    2

    Returns: 1

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: