Statistics

Problem Statement for "BadSubstring"

Problem Statement

Return how many strings containing length characters do not have the substring (quotes for clarity) "ab". The only characters allowed in the strings are 'a', 'b', and 'c'. A substring is any contiguous portion of a string. A substring may be empty, or the entire string.

Definition

Class:
BadSubstring
Method:
howMany
Parameters:
int
Returns:
long
Method signature:
long howMany(int length)
(be sure your method is public)

Constraints

  • length will be between 0 and 44 inclusive.

Examples

  1. 0

    Returns: 1

    The only string of length 0 is the empty string, and it doesn't have "ab" as a substring.

  2. 3

    Returns: 21

    There are 3*3*3=27 possible strings of length 3. 3 begin with ab, and 3 end with ab. The remaining 21 are all good.

  3. 29

    Returns: 1548008755920

  4. 0

    Returns: 1

  5. 1

    Returns: 3

  6. 2

    Returns: 8

  7. 3

    Returns: 21

  8. 4

    Returns: 55

  9. 5

    Returns: 144

  10. 6

    Returns: 377

  11. 7

    Returns: 987

  12. 8

    Returns: 2584

  13. 9

    Returns: 6765

  14. 10

    Returns: 17711

  15. 11

    Returns: 46368

  16. 12

    Returns: 121393

  17. 13

    Returns: 317811

  18. 14

    Returns: 832040

  19. 15

    Returns: 2178309

  20. 16

    Returns: 5702887

  21. 17

    Returns: 14930352

  22. 18

    Returns: 39088169

  23. 19

    Returns: 102334155

  24. 20

    Returns: 267914296

  25. 21

    Returns: 701408733

  26. 22

    Returns: 1836311903

  27. 23

    Returns: 4807526976

  28. 24

    Returns: 12586269025

  29. 25

    Returns: 32951280099

  30. 26

    Returns: 86267571272

  31. 27

    Returns: 225851433717

  32. 28

    Returns: 591286729879

  33. 29

    Returns: 1548008755920

  34. 30

    Returns: 4052739537881

  35. 31

    Returns: 10610209857723

  36. 32

    Returns: 27777890035288

  37. 33

    Returns: 72723460248141

  38. 34

    Returns: 190392490709135

  39. 35

    Returns: 498454011879264

  40. 36

    Returns: 1304969544928657

  41. 37

    Returns: 3416454622906707

  42. 38

    Returns: 8944394323791464

  43. 39

    Returns: 23416728348467685

  44. 40

    Returns: 61305790721611591

  45. 41

    Returns: 160500643816367088

  46. 42

    Returns: 420196140727489673

  47. 43

    Returns: 1100087778366101931

  48. 44

    Returns: 2880067194370816120

  49. 9

    Returns: 6765

  50. 29

    Returns: 1548008755920

  51. 0

    Returns: 1

  52. 44

    Returns: 2880067194370816120

  53. 2

    Returns: 8

  54. 38

    Returns: 8944394323791464

  55. 37

    Returns: 3416454622906707

  56. 43

    Returns: 1100087778366101931

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: