Statistics

Problem Statement

Alice and Bob play the following game. The game board consists of some cells in a row. Each cell is marked either 'A' or 'B'. At the beginning, there are no coins placed on the board – all the cells are empty. Alice and Bob take alternating turns. Alice plays first. In each turn, the current player chooses some contiguous empty cells and places a coin onto each of the chosen cells. The player must always choose at least one cell. The player must never choose all empty cells. In other words, after each turn there must be at least one empty cell.

The following picture shows two examples of placing coins:


The game ends when there is only one cell left without a coin. If that cell is marked 'A', Alice wins. Otherwise, Bob wins. You are given a String cells representing the row of cells. Assuming that both players aim to win and play optimally, return a String containing the name of the winner.

Definition

Class:

RowAndCoins

Method:

getWinner

Parameters:

String

Returns:

String

Method signature:

String getWinner(String cells)

(be sure your method is public)

Constraints

• cells will contain between 2 and 14 characters, inclusive.
• Each character in cells will be either 'A' or 'B'.

Examples

1. "ABBB"

   Returns: "Alice"

   Alice can win by placing coins on three cells marked 'B' in her first turn.

2. "BBBB"

   Returns: "Bob"

3. "BA"

   Returns: "Alice"

4. "BABBABBB"

   Returns: "Bob"

5. "ABABBBABAABBAA"

   Returns: "Alice"

6. "BBBAAABBAAABBB"

   Returns: "Bob"

7. "AA"

   Returns: "Alice"

8. "BA"

   Returns: "Alice"

9. "AB"

   Returns: "Alice"

10. "BB"

    Returns: "Bob"

11. "AAA"

    Returns: "Alice"

12. "BAA"

    Returns: "Alice"

13. "ABA"

    Returns: "Alice"

14. "BBA"

    Returns: "Alice"

15. "AAB"

    Returns: "Alice"

16. "BAB"

    Returns: "Bob"

17. "ABB"

    Returns: "Alice"

18. "BBB"

    Returns: "Bob"

19. "AAAA"

    Returns: "Alice"

20. "BAAA"

    Returns: "Alice"

21. "ABAA"

    Returns: "Alice"

22. "BBAA"

    Returns: "Alice"

23. "AABA"

    Returns: "Alice"

24. "BABA"

    Returns: "Alice"

25. "ABBA"

    Returns: "Alice"

26. "BBBA"

    Returns: "Alice"

27. "AAAB"

    Returns: "Alice"

28. "BAAB"

    Returns: "Bob"

29. "ABAB"

    Returns: "Alice"

30. "BBAB"

    Returns: "Bob"

31. "AABB"

    Returns: "Alice"

32. "BABB"

    Returns: "Bob"

33. "ABBB"

    Returns: "Alice"

34. "BBBB"

    Returns: "Bob"

35. "ABBBA"

    Returns: "Alice"

36. "ABBBB"

    Returns: "Alice"

37. "BBBBA"

    Returns: "Alice"

38. "BBBBB"

    Returns: "Bob"

39. "AAAABA"

    Returns: "Alice"

40. "AAAABB"

    Returns: "Alice"

41. "BAAABA"

    Returns: "Alice"

42. "BAAABB"

    Returns: "Bob"

43. "ABBBABA"

    Returns: "Alice"

44. "ABBBABB"

    Returns: "Alice"

45. "BBBBABA"

    Returns: "Alice"

46. "BBBBABB"

    Returns: "Bob"

47. "ABABAAAA"

    Returns: "Alice"

48. "ABABAAAB"

    Returns: "Alice"

49. "BBABAAAA"

    Returns: "Alice"

50. "BBABAAAB"

    Returns: "Bob"

51. "AAABBBBAA"

    Returns: "Alice"

52. "AAABBBBAB"

    Returns: "Alice"

53. "BAABBBBAA"

    Returns: "Alice"

54. "BAABBBBAB"

    Returns: "Bob"

55. "AABAAABABA"

    Returns: "Alice"

56. "AABAAABABB"

    Returns: "Alice"

57. "BABAAABABA"

    Returns: "Alice"

58. "BABAAABABB"

    Returns: "Bob"

59. "ABABBBBBAAA"

    Returns: "Alice"

60. "ABABBBBBAAB"

    Returns: "Alice"

61. "BBABBBBBAAA"

    Returns: "Alice"

62. "BBABBBBBAAB"

    Returns: "Bob"

63. "ABBABABAABAA"

    Returns: "Alice"

64. "ABBABABAABAB"

    Returns: "Alice"

65. "BBBABABAABAA"

    Returns: "Alice"

66. "BBBABABAABAB"

    Returns: "Bob"

67. "ABBBBAAAAAAAA"

    Returns: "Alice"

68. "ABBBBAAAAAAAB"

    Returns: "Alice"

69. "BBBBBAAAAAAAA"

    Returns: "Alice"

70. "BBBBBAAAAAAAB"

    Returns: "Bob"

71. "AABBBAAAAAABBA"

    Returns: "Alice"

72. "AABBBAAAAAABBB"

    Returns: "Alice"

73. "BABBBAAAAAABBA"

    Returns: "Alice"

74. "BABBBAAAAAABBB"

    Returns: "Bob"

75. "AAAAAAAAAAAAA"

    Returns: "Alice"

76. "AAAAAAAAAAAAB"

    Returns: "Alice"

77. "BAAAAAAAAAAAA"

    Returns: "Alice"

78. "BAAAAAAAAAAAB"

    Returns: "Bob"

79. "ABBBBBBBBBBBA"

    Returns: "Alice"

80. "ABBBBBBBBBBBB"

    Returns: "Alice"

81. "BBBBBBBBBBBBA"

    Returns: "Alice"

82. "BBBBBBBBBBBBB"

    Returns: "Bob"

83. "ABABABABABABA"

    Returns: "Alice"

84. "ABABABABABABB"

    Returns: "Alice"

85. "BBABABABABABA"

    Returns: "Alice"

86. "BBABABABABABB"

    Returns: "Bob"

87. "AABABABABABAA"

    Returns: "Alice"

88. "AABABABABABAB"

    Returns: "Alice"

89. "BABABABABABAA"

    Returns: "Alice"

90. "BABABABABABAB"

    Returns: "Bob"

91. "AAAAAAAAAAAAAA"

    Returns: "Alice"

92. "AAAAAAAAAAAAAB"

    Returns: "Alice"

93. "BAAAAAAAAAAAAA"

    Returns: "Alice"

94. "BAAAAAAAAAAAAB"

    Returns: "Bob"

95. "AAAAAAABAAAAAA"

    Returns: "Alice"

96. "AAAAAAABAAAAAB"

    Returns: "Alice"

97. "BAAAAAABAAAAAA"

    Returns: "Alice"

98. "BAAAAAABAAAAAB"

    Returns: "Bob"

99. "ABBBBBBBBBBBBA"

    Returns: "Alice"

100. "ABBBBBBBBBBBBB"

     Returns: "Alice"

101. "BBBBBBBBBBBBBA"

     Returns: "Alice"

102. "BBBBBBBBBBBBBB"

     Returns: "Bob"

103. "ABBBBBBBABBBBA"

     Returns: "Alice"

104. "ABBBBBBBABBBBB"

     Returns: "Alice"

105. "BBBBBBBBABBBBA"

     Returns: "Alice"

106. "BBBBBBBBABBBBB"

     Returns: "Bob"

107. "ABABABABABABAA"

     Returns: "Alice"

108. "ABABABABABABAB"

     Returns: "Alice"

109. "BBABABABABABAA"

     Returns: "Alice"

110. "BBABABABABABAB"

     Returns: "Bob"

111. "AABABABABABABA"

     Returns: "Alice"

112. "AABABABABABABB"

     Returns: "Alice"

113. "BABABABABABABA"

     Returns: "Alice"

114. "BABABABABABABB"

     Returns: "Bob"