Statistics

Problem Statement for "MostSubstrings"

Problem Statement

Let C(Haystack, Needle) be the number of different (possibly overlapping) occurrences of the string Needle in the string Haystack as a contiguous substring.

For example, C("ababababa", "aba") = 4, C("cat", "catastrophy") = 0, and C("canyoudancecancan", "can") = 3.


Given is a string S of lowercase English letters and an int L.

Let Cmax be the largest possible number of times S may occur in a string of length L. In other words, Cmax is the maximum value of C(T, S) taken over all strings T of length L.


Count all strings T made of exactly L lowercase English letters such that C(T, S) = Cmax. Return their count modulo 10^9 + 7.

Definition

Class:
MostSubstrings
Method:
count
Parameters:
String, int
Returns:
int
Method signature:
int count(String S, int L)
(be sure your method is public)

Constraints

  • S will have between 1 and 100 characters, inclusive.
  • Each character of S will be a lowercase English letter.
  • L will be between 1 and 1000, inclusive.

Examples

  1. "helloworld"

    7

    Returns: 31810120

    Each of the 26^7 possible strings of length 7 contains 0 occurrences of the string "helloworld", so each of them is optimal. The return value is (26^7 modulo (10^9 + 7)).

  2. "aaaa"

    13

    Returns: 1

    The only optimal string is "aaaaaaaaaaaaa" (13 'a's).

  3. "dogecoin"

    17

    Returns: 78

    The optimal answers are strings of the form "Xdogecoindogecoin", "dogecoinXdogecoin", and "dogecoindogecoinX", where X can be any single letter.

  4. "decode"

    11

    Returns: 52

    Now the optimal solutions are strings of the form "Xdecodecode" and "decodecodeX".

  5. "abadeaba"

    8

    Returns: 1

  6. "abadeaba"

    9

    Returns: 52

  7. "abadeaba"

    10

    Returns: 2028

  8. "abadeaba"

    11

    Returns: 70304

  9. "abadeaba"

    12

    Returns: 2284880

  10. "abadeaba"

    13

    Returns: 1

  11. "abadeaba"

    14

    Returns: 52

  12. "abadeaba"

    15

    Returns: 2029

  13. "abadeaba"

    16

    Returns: 70357

  14. "abadeaba"

    17

    Returns: 2286986

  15. "abadeaba"

    18

    Returns: 1

  16. "abadeaba"

    19

    Returns: 52

  17. "abadeaba"

    20

    Returns: 2030

  18. "abadeaba"

    21

    Returns: 70410

  19. "abadeaba"

    22

    Returns: 2289093

  20. "abadeaba"

    23

    Returns: 1

  21. "abadeaba"

    24

    Returns: 52

  22. "abadeaba"

    25

    Returns: 2031

  23. "abadeaba"

    26

    Returns: 70463

  24. "abadeaba"

    27

    Returns: 2291201

  25. "abadeaba"

    28

    Returns: 1

  26. "abadeaba"

    29

    Returns: 52

  27. "abadeaba"

    30

    Returns: 2032

  28. "abadeaba"

    31

    Returns: 70516

  29. "abadeaba"

    32

    Returns: 2293310

  30. "abadeaba"

    33

    Returns: 1

  31. "abadeaba"

    34

    Returns: 52

  32. "abadeaba"

    35

    Returns: 2033

  33. "abadeaba"

    36

    Returns: 70569

  34. "abadeaba"

    37

    Returns: 2295420

  35. "a"

    1000

    Returns: 1

  36. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    999

    Returns: 1

  37. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000

    Returns: 3731860

  38. "abacabadabacabaeabacabadabacaba"

    309

    Returns: 162410418

  39. "abacabadabacabaeabacabadabacaba"

    310

    Returns: 254480960

  40. "abacabadabacabaeabacabadabacaba"

    311

    Returns: 443568048

  41. "abacabadabacabaeabacabadabacaba"

    175

    Returns: 1

  42. "qqqq"

    762

    Returns: 1

  43. "pqpppqqpqqppqq"

    990

    Returns: 317987481

  44. "qq"

    807

    Returns: 1

  45. "pppqp"

    685

    Returns: 1

  46. "qppqpqpqqqpqqpqqqqpppqqqpqpp"

    780

    Returns: 2028

  47. "pqqqqpqqqpppqqppqppppqqpqqppqpqpqpppq"

    602

    Returns: 74112896

  48. "ppppqpppqpppqpq"

    622

    Returns: 599413597

  49. "qpqqppqqqqqpppqqpqpq"

    901

    Returns: 583312098

  50. "ppqqpqppqqqppqpqqqppqqqqpppqqqqppqqpqpqqqpqpqqqqqppqppqqqqqpqpp"

    716

    Returns: 377808718

  51. "qpqqpqq"

    815

    Returns: 52

  52. "qppppqqppqpqpppqpqqqq"

    874

    Returns: 899441233

  53. "p"

    544

    Returns: 1

  54. "ppqqqpqqqpqqpp"

    985

    Returns: 214984199

  55. "qpqqpqpqpppqqppqpqpqqpqpqpqppppppppppppqqpqqpqpqppppqpqqqqqqqqp"

    599

    Returns: 567592067

  56. "qpqp"

    549

    Returns: 52

  57. "pqpqqqp"

    977

    Returns: 233358520

  58. "pq"

    666

    Returns: 1

  59. "qp"

    524

    Returns: 1

  60. "ppqqppqqppqpqqqpqqqqqpqpqqppqpqqpqqqppqqppppqqpqppp"

    628

    Returns: 281187062

  61. "qqpqqpqqqpppqpppppqqpp"

    994

    Returns: 822246304

  62. "qppqqpq"

    737

    Returns: 118562250

  63. "pqqqpqqpqpppp"

    787

    Returns: 487665222

  64. "pq"

    718

    Returns: 1

  65. "ppqqqppppppppp"

    765

    Returns: 704788120

  66. "qqp"

    585

    Returns: 1

  67. "pppqqqqqqqppqqqqqqqq"

    701

    Returns: 936

  68. "qpqqpppq"

    980

    Returns: 860866265

  69. "ppqqppqqqpqqqqppppqpqqpqppppqpppqqpqppqpqqpqpppqqpqqp"

    692

    Returns: 901376485

  70. "qqqpp"

    651

    Returns: 3406

  71. "pppqqqpqppqpp"

    849

    Returns: 1

  72. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    999

    Returns: 995680885

  73. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    1000

    Returns: 1

  74. "ababababababababababababccccccccccccccccccccccccccccccccccccccccccccccccccccabababababababababababab"

    859

    Returns: 52787161

  75. "decode"

    13

    Returns: 70382

  76. "ababbbbaaabbbbabbabaaaabaaabaaabaaababbbbaaaaaabababbbaaaaaabbbbabbbbababbbbababababaabbabaaababbbaa"

    1000

    Returns: 218235411

  77. "abbba"

    11

    Returns: 2106

  78. "abcda"

    1000

    Returns: 6773000

  79. "abcdef"

    28

    Returns: 31988320

  80. "abbbbba"

    28

    Returns: 82785

  81. "aabaa"

    9

    Returns: 53

  82. "aaaaaaskjhdfilkjswhdnfkljsndfkjajajsssssssssssssssaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000

    Returns: 829165020

  83. "abca"

    8

    Returns: 53

  84. "periodperiodperiodperiodperiodperiodperiodperioabwxyzperiodperiodperiodperiodperiodperiodperiodperio"

    1000

    Returns: 517236919

  85. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000

    Returns: 1

  86. "abababababababababababababababababababababababababababababababababababababababababababababababababab"

    1000

    Returns: 1

  87. "aaaaa"

    3

    Returns: 17576

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: