Statistics

Problem Statement for "SuspiciousStrings"

Problem Statement

You work at a company specializing in internet-related technologies, and your current project is a spam filter. This filter determines whether or not a string contains spam-like information using a "spam-words-dictionary" (SWD). If an input string contains at least one word from this dictionary as a substring, the filter considers it to be spam-suspicious. (Note: an entire string is considered a substring of itself.)

You've decided to solve a more challenging problem: how many unique strings of length n, composed entirely of lowercase letters, are spam-suspicious for a given SWD? You are given a String[] dictionary, each element of which is a word from the SWD, and an int n. Return the answer modulo 10000.

Definition

Class:
SuspiciousStrings
Method:
getAmount
Parameters:
String[], int
Returns:
int
Method signature:
int getAmount(String[] dictionary, int n)
(be sure your method is public)

Notes

  • "Substring" is formed of consecutive letters (so, it's NOT a subsequence of letters).
  • "x modulo y" means the remainder of x divided by y.

Constraints

  • dictionary will contain between 1 and 10 elements, inclusive.
  • Each element of dictionary will contatin only lowercase letters ('a'-'z').
  • Each element of dictionary will contain between 1 and 10 characters, inclusive.
  • n will be between 1 and 2147483647, inclusive.

Examples

  1. {"x"}

    1

    Returns: 1

    All one character length strings are allowed except for "x".

  2. {"ab","bb"}

    2

    Returns: 2

    Suspicious strings are "ab" and "bb".

  3. {"ab","bb"}

    5

    Returns: 6350

  4. {"aab","bba"}

    5

    Returns: 4054

  5. {"xxxxxx","xxx","x","yyxyy","xxxyxxx","y","yx","xy","zzzzzzzzzz"}

    5

    Returns: 8752

  6. {"aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee", "ffffffffff", "gggggggggg", "hhhhhhhhhh", "xxxxxxxxxx", "zzzzzzzzzz"}

    2147483647

    Returns: 5040

  7. {"xy","xx","yx"}

    2

    Returns: 3

  8. {"testtest","test"}

    18

    Returns: 3022

  9. {"aaabbb","bbbaaa"}

    16

    Returns: 9396

  10. {"ssssssssss"}

    9

    Returns: 0

  11. {"pppppppppp"}

    10

    Returns: 1

  12. {"tttttttttt","yyyyyyyyyy","kkkkkkkkkk","nnnnnnnnnn","aaaaaaaaaa","mmmmmmmmmm", "qqqqqqqqqq","pppppppppp","bbbbbbbbbb","jjjjjjjjjj"}

    1073741823

    Returns: 2720

  13. {"muhmx","tbszq","lsdxrmzxq","jbocsznxjb","mmpvk","ewxzuacchf"}

    169465347

    Returns: 890

  14. {"kyyrknywut","v","qcbbyznoo","fplcufh","kbpv","wzy","lbigab","bhwpsmlpu"}

    321787702

    Returns: 1720

  15. {"mgkkikj","ljghhji","ihhmmmmi","mlmmmlk","kmhililj","ikimk","ljjmkgh","jlhgl","jlhhm"}

    8

    Returns: 1122

  16. {"kmglk","ikgkkk","ighgmkhmg","mmilg","jkjiilllkm","jkkiiljkmi","kkmklggg","ghklhkhill","ilkmijg","iigilkmk"}

    8

    Returns: 2690

  17. {"kmhmkgh","hjhmgkjljg","hmmmmlj","klmhjmj","iimhlklihm","jkkjgh","mhhlhj","iiimmgjki","mkkhmkj"}

    1

    Returns: 0

  18. {"ilhjg","ghghmlhhkg","lilikkmklg","lmlhhkji","klhmgi","jlhigl","glhigkl","llkhhmjglg"}

    3

    Returns: 0

  19. {"gikgki","kikhiihg","kljhkilk","jghmjlj","ikhiihmgm","llklhlik","mgimiimmj","kmiliiki","gkmjij","glhghjmk"}

    4

    Returns: 0

  20. {"lmllkgj","iilkmjjgg","mljljjll","mgjikgmgk","hljiighjki","jlljl","iglgmgj","hmgmimgl","kilhmk"}

    9

    Returns: 9294

  21. {"khlhlhjm","lllmkgh","ilglkjhg","glkijmgigi","ijgmhg","kgiggjih","kjhmjkjlj","hmmjhhjlmm"}

    4

    Returns: 0

  22. {"vhef","xdunklm","zxassx","soruhb","wm","dpzsktcxd"}

    1277958538

    Returns: 7072

  23. {"nautfkkvz","tlvx","tctq"}

    391619553

    Returns: 1104

  24. {"kfo","vryucpgqkf","sllgxrb","t","oimjfmggps","ddtizzclqr","vnwihj"}

    1658970893

    Returns: 3646

  25. {"ostkusve","boiyyn","gcu","xvqdayjl","hfzarfp"}

    925344302

    Returns: 5360

  26. {"wmemiroj"}

    1993813358

    Returns: 2688

  27. {"vsf","w","rw","agblir","ymhuvrewyc","wq","vjhix","izmyrl","ngryeo","u"}

    1

    Returns: 2

  28. {"fuecbqdcr","tlzuf","wbiz","x","itdy","yob"}

    1228691106

    Returns: 2613

  29. {"msbt","seiscoi","as","bmffr","zbxfmzxhtt","odubw","qknbljs","fossgi"}

    1306212165

    Returns: 8086

  30. {"qvmacr","pfsxokya","dwluixhsu","seobrzog","anvsikkz"}

    1517632626

    Returns: 9698

  31. {"n","jvuwjg","v","vpfsmjjcdb","hokhikusco","ase","bwtdisg","uheofhr"}

    1568770062

    Returns: 9832

  32. {"kny","d","kwwcoj","yg","nu"}

    1623644892

    Returns: 9688

  33. {"wlbqrb","z","tplbu","nmlkwydfwc","pd","ugkumpjmeg"}

    2067419357

    Returns: 1229

  34. {"qco","vdaaymouu","dlxawy"}

    2134972478

    Returns: 1708

  35. {"ommvwau","ftjopbawb"}

    282435424

    Returns: 880

  36. {"v","wgegxzedc","bnewfi","vnatn","tgrgrfftf","bfpbm","sevrgqox","zsmp"}

    19386926

    Returns: 3090

  37. {"s","qetlqiijja","xtjm","n","pmnt","eb"}

    1591803662

    Returns: 9906

  38. {"rsyasohm","ga","ld","ulx"}

    1652704556

    Returns: 3167

  39. {"dmauhuccld","lgvkrpn","eippb","rdox","azbodtz","vdaas","gthqjwr","kpnz","uvtxpb","qtrsx"}

    722997388

    Returns: 6835

  40. {"xxjs","gecvodpc","vxmyi","blvss","fehlixls","hcup","kbcipbrsb"}

    345283398

    Returns: 1300

  41. {"wybq","i","wzwxxacycf","lspottmp","oghjxzz","rk"}

    1376994792

    Returns: 9428

  42. {"ezffc","gcghucg","ygppmhprh","edi"}

    1656385931

    Returns: 2722

  43. {"kw"}

    1335452692

    Returns: 1627

  44. {"qgea"}

    279550175

    Returns: 7392

  45. {"xsspdgjiel","gigd","tfceik","htbajv","gck","fqgo","av","kcmsz"}

    697814744

    Returns: 2622

  46. {"gtqz"}

    1834801500

    Returns: 8833

  47. {"ps","hbxahxjfs","p","attdaruca"}

    594265473

    Returns: 3277

  48. {"fddpbhvka","onl","ajyfq","smmilypwu","kypzjodat","hvk","dfontgnty","gsopfvjfuq","khnjv"}

    435643524

    Returns: 5918

  49. {"pla","idjymsa","fihxje","dmpsmoiabg","alqxvfu","skkxdmjt","rdpomjgg","qc"}

    701202974

    Returns: 209

  50. {"chuihqsnld","ogckzulnsa","coqxypqlen","izzvhdskjf","ryoiqqydvv","gdvqqklfia","twyohryspc","dnaczekoge","dvdrhfmjbh","tpkcrgnrto"}

    1090793943

    Returns: 1456

  51. {"itwkdmvftz","cgkfjncaww","uqcsxrzazd","vpgwcxepdv","pqdirrtnhq","nlmrbatgth","joufmpbpgr","fjdivsjjlf","ryslkvresu","ulgixrmwfd"}

    1073741823

    Returns: 9264

  52. {"puztwtcrjf","wlmxxcvcpw","zoysgcgvmi","kqhebgkbkb","kqmglnxzvr","bvfbvmxcbw","coevggnlem","ianhspnvbg","dpdtazoyyl","eqvicahtcl"}

    737583858

    Returns: 2643

  53. {"fehjubimwm","tnpwiagnyg","xuxiojdytt","jfdeolhtch","rsyrxgofvk","blnfifokwx","auyfsdvwxp","oeskbqlena","opdcgzinsy","fkvaumznpt"}

    81228650

    Returns: 5456

  54. {"vlngmxskeg","mhvtrwhkca","orkbypecwo","ffnpgloepa","tmxhcaujot","urxaxcmzjg","subwbjxpgu","lqtoerlemh","dabyzilbja","czcepepdgc"}

    1492698180

    Returns: 9811

  55. {"aabbbabaab","aaabbabbba","bbababaaba","abaabbaaaa","bbabbbabba","aaaabbabaa","babbbababa","abbabbabbb","bbbbbabbba","baabaaaaba"}

    729788645

    Returns: 2049

  56. {"aaaaaaaabb","aaaaabbabb","abaabababa","abbabbbbab","baaabaabab","ababbbaaab","aabbabaaaa","aabbbabbbb","babbaaabab","babbabbabb"}

    1992504133

    Returns: 2904

  57. {"baabbbbbba","bbaaaaaaaa","babaabbaba","bbbbabbbaa","bbabaabaaa","babbaaaaab","babbbabbab","aaaaaaabab","aaaaababab","babaababaa"}

    1073741824

    Returns: 4727

  58. {"bbaabbaaaa","abaaabbaab","aaabababbb","baabaaaaaa","aaaababbbb","abaaaabaaa","bbabbbbaba","babaabbbba","baabababbb","bbbbabbbbb"}

    1667690330

    Returns: 2295

  59. {"aabaabbaba","baabbbabba","aabaabbaab","abbbbbbbaa","bbaaabaaab","aabbbaabab","aababababb","abababbaab","bbaaabbabb","aaaaababba"}

    804359459

    Returns: 7064

  60. {"baaaabbbba","abbbabbbbb","baababaabb","bbabaaabba","bbabaababb","aaabbbabab","bbbbbaaaaa","aaaaaaaaba","aabbabbabb","bbbabaabab"}

    330893685

    Returns: 5364

  61. {"aaaabbbbab","bbbabbabab","baaababbba","baababbaba","aaaaabbaaa","abbbababaa","bbaabaaaab","aabaabbbba","babbbabaab","aabbbababb"}

    1233

    Returns: 9798

  62. {"abcdefghij","bcdefghijk","cdefghijkl","defghijklm","efghijklmn","fghijklmno","ghijklmnop","hijklmnopq","ijklmnopqr","jklmnopqrs"}

    1642649847

    Returns: 936

  63. {"abcdefghij","klmnopqrst","uvwxyz"}

    1000059993

    Returns: 1984

  64. {"q"}

    2147483647

    Returns: 551

  65. {"fifi","fi"}

    4

    Returns: 2027

  66. {"test","testtest"}

    8

    Returns: 4827

  67. {"test","testtest"}

    4

    Returns: 1

  68. {"test","testtest"}

    10

    Returns: 6073

  69. {"fi","fifi"}

    2

    Returns: 1

  70. {"fi","fifi"}

    4

    Returns: 2027

  71. {"ngwrtuodnm","pthqbgonm","zroqnve","algmeibh","algoritm","algo","nve","nm","qbg"}

    7777564

    Returns: 1180

  72. {"abcd","abcd"}

    4

    Returns: 1

  73. {"aa","bb","aa"}

    2

    Returns: 2

  74. {"topcoder","codertop","topcoder"}

    10

    Returns: 4056

  75. {"abcd","ghju","abcd"}

    5

    Returns: 104

  76. {"tiptip","tiptop","toptop","tiptip"}

    1000000000

    Returns: 1552

  77. {"killbill","killbill","killbill","killbill","killbill","killbill", "killbill","killbill","killbill","killbill"}

    777478

    Returns: 8368

  78. {"tttttttttt","yyyyyyyyyy","kkkkkkkkkk","nnnnnnnnnn","aaaaaaaaaa","mmmmmmmmmm", "uuuuuuuuuu","pppppppppp","bbbbbbbbbb","jjjjjjjjjj"}

    2147483647

    Returns: 5040

  79. {"tttttttttt","yyyyyyyyyy","kkkkkkkkkk","nnnnnnnnnn","aaaaaaaaaa","mmmmmmmmmm", "uuuuuuuuuu","pppppppppp","tttttttttt","jjjjjjjjjj"}

    2147483647

    Returns: 8630

  80. {"x" }

    1

    Returns: 1

  81. {"cacaac", "aaccac", "ccacca", "aaaccacac", "caacaaccc", "acaacacaa", "aananabva", "assdfafjj", "assffaasd", "ccacaass" }

    1999999973

    Returns: 1466

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: