Statistics

Problem Statement for "ThreeSameLetters"

Problem Statement

A string is called a block if it consists of exactly three equal letters.

A string is called a one-block string if it contains exactly one contiguous substring that is a block.

For example:

  • "aaa" and "abcccdd" are one-block strings
  • "noblocks" and "ababab" are not one-block strings, as they do not contain any blocks
  • "xxxyyyzzz" and "baaaad" are not one-block strings, as each of them contains at least two blocks

Note that the two blocks in "baaaad" overlap partially.

You are given the ints L and S. If we can only use the first S lowercase letters of the English alphabet, how many different one-block strings of length L are there? Return their count modulo 10^9 + 7.

Definition

Class:
ThreeSameLetters
Method:
countStrings
Parameters:
int, int
Returns:
int
Method signature:
int countStrings(int L, int S)
(be sure your method is public)

Constraints

  • L will be between 1 and 26, inclusive.
  • S will be between 1 and 26, inclusive.

Examples

  1. 3

    7

    Returns: 7

    The seven one-block strings are "aaa", "bbb", "ccc", ..., "ggg".

  2. 4

    2

    Returns: 4

    The four one-block strings are "aaab", "abbb", "baaa", and "bbba".

  3. 2

    17

    Returns: 0

  4. 10

    11

    Returns: 410199993

    Don't forget to do the calculations modulo 10^9 + 7.

  5. 26

    26

    Returns: 450838424

  6. 12

    1

    Returns: 0

  7. 1

    17

    Returns: 0

  8. 15

    1

    Returns: 0

  9. 13

    17

    Returns: 918438936

  10. 1

    6

    Returns: 0

  11. 25

    1

    Returns: 0

  12. 23

    26

    Returns: 81179699

  13. 2

    5

    Returns: 0

  14. 1

    11

    Returns: 0

  15. 14

    18

    Returns: 305859625

  16. 19

    14

    Returns: 981070515

  17. 25

    26

    Returns: 604751851

  18. 14

    1

    Returns: 0

  19. 24

    1

    Returns: 0

  20. 13

    20

    Returns: 351522822

  21. 1

    1

    Returns: 0

  22. 23

    25

    Returns: 636466965

  23. 3

    2

    Returns: 2

  24. 8

    2

    Returns: 76

  25. 24

    24

    Returns: 440867539

  26. 17

    13

    Returns: 3412148

  27. 1

    12

    Returns: 0

  28. 26

    1

    Returns: 0

  29. 3

    1

    Returns: 1

  30. 7

    8

    Returns: 130144

  31. 1

    21

    Returns: 0

  32. 26

    24

    Returns: 452207454

  33. 1

    26

    Returns: 0

  34. 26

    23

    Returns: 752832258

  35. 2

    1

    Returns: 0

  36. 1

    15

    Returns: 0

  37. 5

    1

    Returns: 0

  38. 14

    22

    Returns: 920298662

  39. 24

    18

    Returns: 879371733

  40. 1

    16

    Returns: 0

  41. 1

    5

    Returns: 0

  42. 2

    2

    Returns: 0

  43. 1

    10

    Returns: 0

  44. 4

    1

    Returns: 0

  45. 11

    4

    Returns: 1092204

  46. 7

    1

    Returns: 0

  47. 11

    9

    Returns: 681524210

  48. 17

    1

    Returns: 0

  49. 25

    25

    Returns: 533730745

  50. 1

    19

    Returns: 0

  51. 23

    24

    Returns: 159738617

  52. 6

    1

    Returns: 0

  53. 16

    1

    Returns: 0

  54. 24

    25

    Returns: 266552732

  55. 19

    1

    Returns: 0

  56. 17

    17

    Returns: 915505184

  57. 1

    3

    Returns: 0

  58. 15

    19

    Returns: 503096862

  59. 18

    1

    Returns: 0

  60. 1

    20

    Returns: 0

  61. 26

    25

    Returns: 320023700

  62. 25

    23

    Returns: 210823538

  63. 12

    20

    Returns: 492859170

  64. 1

    25

    Returns: 0

  65. 18

    12

    Returns: 44072617

  66. 21

    1

    Returns: 0

  67. 1

    14

    Returns: 0

  68. 12

    3

    Returns: 164928

  69. 1

    23

    Returns: 0

  70. 26

    26

    Returns: 450838424

  71. 20

    1

    Returns: 0

  72. 1

    4

    Returns: 0

  73. 2

    3

    Returns: 0

  74. 1

    9

    Returns: 0

  75. 23

    1

    Returns: 0

  76. 4

    2

    Returns: 4

  77. 25

    24

    Returns: 17938294

  78. 12

    19

    Returns: 326765969

  79. 1

    18

    Returns: 0

  80. 1

    7

    Returns: 0

  81. 22

    1

    Returns: 0

  82. 3

    4

    Returns: 4

  83. 2

    4

    Returns: 0

  84. 9

    1

    Returns: 0

  85. 24

    26

    Returns: 858429087

  86. 26

    16

    Returns: 766559247

  87. 2

    26

    Returns: 0

  88. 1

    2

    Returns: 0

  89. 3

    3

    Returns: 3

  90. 8

    1

    Returns: 0

  91. 4

    4

    Returns: 24

  92. 11

    1

    Returns: 0

  93. 19

    25

    Returns: 611309022

  94. 24

    23

    Returns: 901818760

  95. 11

    18

    Returns: 855044556

  96. 1

    24

    Returns: 0

  97. 1

    13

    Returns: 0

  98. 10

    1

    Returns: 0

  99. 13

    1

    Returns: 0

  100. 12

    15

    Returns: 705239742

  101. 1

    22

    Returns: 0

  102. 23

    23

    Returns: 894541348

  103. 1

    8

    Returns: 0

  104. 8

    8

    Returns: 1223824

  105. 4

    3

    Returns: 12

  106. 3

    1

    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: