Statistics

Problem Statement

Input string: "HELLO" (quotes for clarity only)
Pattern:      O
             OLO
            OLLLO
           OLLELLO
          OLLEHELLO
           OLLELLO
            OLLLO
             OLO
              O



Input string: "TC" (quotes for clarity only)
Pattern:      C
             CTC
              C   



Input string: "ABCD" (quotes for clarity only)
Pattern:      D
             DCD
            DCBCD
           DCBABCD
            DCBCD
             DCD
              D



After constructing the patterns, I noticed something interesting. Starting with the first letter of the input string (which appears only once in the very center of the pattern), I can trace a path outwards toward the edges, spelling out the original input string. Of course, I only move Up, Down, Left and Right from any letter. I'm now perplexed because I want to know how many ways the original input string can be spelled out in the pattern. I must always end at an edge, and I can't go over one letter more than once while spelling a word.




Create a class WordPattern containing the method countWords which takes a String word as input. The method should return a long which is the number of ways the original input can be spelled out in the pattern according to my rules.

Definition

Class:

WordPattern

Method:

countWords

Parameters:

String

Returns:

long

Method signature:

long countWords(String word)

(be sure your method is public)

Notes

• Remember, I only move Up, Down, Left and Right from any letter to the next letter and never use a letter twice.

Constraints

• word will contain between 1 and 50 characters inclusive.
• word will contain only uppercase letters ('A'-'Z').

Examples

1. "HELLO"

   Returns: 60

2. "TC"

   Returns: 4

3. "ABCDEFGHIJKLMNOPQRST"

   Returns: 2097148

4. "ALKSJDLGHSDGH"

   Returns: 16380

5. "SDG"

   Returns: 12

6. "A"

   Returns: 1

7. "AB"

   Returns: 4

8. "ABC"

   Returns: 12

9. "ABCD"

   Returns: 28

10. "ABCDE"

    Returns: 60

11. "ABCDEF"

    Returns: 124

12. "ABCDEFG"

    Returns: 252

13. "ABCDEFGH"

    Returns: 508

14. "ABCDEFGHI"

    Returns: 1020

15. "ABCDEFGHIJ"

    Returns: 2044

16. "ABCDEFGHIJK"

    Returns: 4092

17. "ABCDEFGHIJKL"

    Returns: 8188

18. "ABCDEFGHIJKLM"

    Returns: 16380

19. "ABCDEFGHIJKLMN"

    Returns: 32764

20. "ABCDEFGHIJKLMNO"

    Returns: 65532

21. "ABCDEFGHIJKLMNOP"

    Returns: 131068

22. "ABCDEFGHIJKLMNOPQ"

    Returns: 262140

23. "ABCDEFGHIJKLMNOPQR"

    Returns: 524284

24. "ABCDEFGHIJKLMNOPQRS"

    Returns: 1048572

25. "ABCDEFGHIJKLMNOPQRST"

    Returns: 2097148

26. "ABCDEFGHIJKLMNOPQRSTU"

    Returns: 4194300

27. "ABCDEFGHIJKLMNOPQRSTUV"

    Returns: 8388604

28. "ABCDEFGHIJKLMNOPQRSTUVW"

    Returns: 16777212

29. "ABCDEFGHIJKLMNOPQRSTUVWX"

    Returns: 33554428

30. "ABCDEFGHIJKLMNOPQRSTUVWXY"

    Returns: 67108860

31. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    Returns: 134217724

32. "ABCDEFGHIJKLMNOPQRSTUVWXYZA"

    Returns: 268435452

33. "ABCDEFGHIJKLMNOPQRSTUVWXYZAB"

    Returns: 536870908

34. "ABCDEFGHIJKLMNOPQRSTUVWXYZABC"

    Returns: 1073741820

35. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCD"

    Returns: 2147483644

36. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDE"

    Returns: 4294967292

37. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEF"

    Returns: 8589934588

38. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFG"

    Returns: 17179869180

39. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGH"

    Returns: 34359738364

40. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHI"

    Returns: 68719476732

41. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJ"

    Returns: 137438953468

42. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJK"

    Returns: 274877906940

43. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKL"

    Returns: 549755813884

44. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLM"

    Returns: 1099511627772

45. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMN"

    Returns: 2199023255548

46. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNO"

    Returns: 4398046511100

47. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOP"

    Returns: 8796093022204

48. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQ"

    Returns: 17592186044412

49. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQR"

    Returns: 35184372088828

50. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS"

    Returns: 70368744177660

51. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRST"

    Returns: 140737488355324

52. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTU"

    Returns: 281474976710652

53. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRTSTUV"

    Returns: 1125899906842620

54. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRTSTUVW"

    Returns: 2251799813685244

55. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 68719476732

56. "AA"

    Returns: 4

57. "AAAAAAAAAAAAAAA"

    Returns: 65532

58. "A"

    Returns: 1

59. "R"

    Returns: 1

60. "TC"

    Returns: 4

61. "K"

    Returns: 1

62. "XX"

    Returns: 4

63. "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJ"

    Returns: 137438953468

64. "T"

    Returns: 1

65. "C"

    Returns: 1

66. "H"

    Returns: 1

67. "ABCDEFGHIJKLMNOPQRSTUVWXYZABBBHIZZZEPPPOAAQUTNNYII"

    Returns: 2251799813685244

68. "HELLO"

    Returns: 60

69. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 2251799813685244

70. "X"

    Returns: 1

71. "MADAM"

    Returns: 60

72. "ABCDEEFGEADESWJFOADNDOSMGSEOSKDLSSAKEOFMMMMMMMMMMM"

    Returns: 2251799813685244