Statistics

Problem Statement for "BallotCounting"

Problem Statement

An election has just finished. There were two candidates: A and B. Each voter voted for one of the two candidates. The winner will be the candidate who received more votes. Thus, there are three possibilities for the outcome: A won, B won, or the election is a tie.

You are a journalist who observes the election committee. Your task is to report the outcome of the election as quickly as possible.


The votes cast are given in the String votes: each 'A' is a vote for candidate A and each 'B' is a vote for candidate B. You know the total number of votes cast (i.e., the length of the string votes).

The election committee is counting the votes in the order in which they are given in the string. Luckily, you just realized that you probably won't have to be there until the very end. It is quite likely that you will already know the outcome of the election before the last vote has been counted.

For example, suppose the votes cast are votes = "AABAABAAB". The election committee will count the votes in this order: one vote for A, another vote for A, then a vote for B, and so on. After they count the first seven votes ("AABAABA") you will already know the election result. (Candidate A is leading with five votes to two, and the remaining two votes can no longer change the winner of the election.)


Return the smallest X such that the result of the election will be known after the first X votes have been counted.

Definition

Class:
BallotCounting
Method:
count
Parameters:
String
Returns:
int
Method signature:
int count(String votes)
(be sure your method is public)

Constraints

  • votes will have between 1 and 50 characters, inclusive.
  • Each character in votes will be 'A' or 'B'.

Examples

  1. "AAAAABBBBB"

    Returns: 10

    You have to wait until all ten votes have been counted. The final result is a tie.

  2. "AAAAABBBBA"

    Returns: 10

    Again, you have to wait until all ten votes have been counted. After nine votes the counting is in exactly the same state as in Example 0: A has 5 votes, B has 4 votes, and one vote remains to be counted. In this case, A got the last vote and won the election.

  3. "AAAAA"

    Returns: 3

    This election is a landslide. After we see three of the five votes, we are already sure that A will be the winner.

  4. "AAAAAA"

    Returns: 4

    This is very similar to the previous example. Note that after three votes it is still possible that the election will be a tie, we have to see the fourth A to be sure.

  5. "AAABAA"

    Returns: 5

  6. "AABAABAAB"

    Returns: 7

    This is the example from the problem statement.

  7. "A"

    Returns: 1

  8. "B"

    Returns: 1

  9. "BB"

    Returns: 2

  10. "BABABBB"

    Returns: 6

    Here B is the winner of the election and we will know it before we see the last vote.

  11. "BBBBBBBBBBABBABABBBBABBB"

    Returns: 15

  12. "BBBBAABBBBBBBBBB"

    Returns: 11

  13. "BAABABBBBBBABA"

    Returns: 11

  14. "ABBABBBBBABABABBBABABBBABBABABABBABBABAABBBAAA"

    Returns: 36

  15. "AAAABAAABAABABBAAAAAAABAAAAAAABAAA"

    Returns: 24

  16. "BBABBBABABABBBBBBBBBBBBABAB"

    Returns: 18

  17. "ABABABAAAAA"

    Returns: 9

  18. "BBBBBBBBBBBBBBBBBBABB"

    Returns: 11

  19. "ABBBBAABABBBABBBBAABBBABAAAA"

    Returns: 22

  20. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 16

  21. "BABBBABBAABABABAAABBBAAABABBAAAAABBABBBABAABBAABB"

    Returns: 49

  22. "BAAAAAAAABAABBBAABABBABBBBBBBBBABBA"

    Returns: 33

  23. "BABA"

    Returns: 4

  24. "AABABAABABABAAABBBBABABAAABABABAB"

    Returns: 30

  25. "ABAABBAABAAAAABBABBAABAAAABABABBA"

    Returns: 26

  26. "BBBBBABABBABBABBBABBBABBBABAABAAAA"

    Returns: 24

  27. "ABAAAABAAAA"

    Returns: 8

  28. "BABABABAAAABAAAABBBA"

    Returns: 16

  29. "BBBBAAAABAABABAAAAABAAABBAAAABAABA"

    Returns: 28

  30. "BBBBBBAAABABBAABABAAABBAABBBAAAABAAAAABBABAB"

    Returns: 43

  31. "BABBBBBAABBBBBAABAABABBBBABBBBBBAABAAAAABBAA"

    Returns: 32

  32. "BB"

    Returns: 2

  33. "BA"

    Returns: 2

  34. "BAABABBBBABAAAAAABABBAABBABBBAAABBBB"

    Returns: 36

  35. "BBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 13

  36. "BBB"

    Returns: 2

  37. "BBAABBBBBBBABB"

    Returns: 10

  38. "AAAAAAAAAAAAAAAAAAAAABAAAAAAABAAAAAAAAAAAAAAAAAA"

    Returns: 26

  39. "BAABABAAABBBAAABAAAAABBBAABAABBAB"

    Returns: 28

  40. "BABB"

    Returns: 4

  41. "AAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAA"

    Returns: 20

  42. "BABABBAABAAAABAA"

    Returns: 15

  43. "AAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 22

  44. "ABBAAABABAABAAAAAAAABA"

    Returns: 17

  45. "AABAAAAAAABAAAAAAABAAAAABAAAAAAAAAABAAABA"

    Returns: 24

  46. "BBBBBBBBABBBBBBBBBAABBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 25

  47. "AAAAAAAAAAAAAAAAA"

    Returns: 9

  48. "BBBBBABBBAABBBBBBABBBBBBBBBBBABBBB"

    Returns: 22

  49. "AAABABAABBBABABAABBBBABBAABABBB"

    Returns: 30

  50. "ABBBBBABABBBB"

    Returns: 10

  51. "ABBBBBBBBBBBBBBBBABBBBAABBBBBBBBABBBBBB"

    Returns: 22

  52. "BAABAABABAAAABB"

    Returns: 12

  53. "BABBAAAAAAAAA"

    Returns: 10

  54. "BBBBBBABABBBBBBBBBBAB"

    Returns: 13

  55. "AAAAAAAAAAAAAA"

    Returns: 8

  56. "ABABBBBBBBBBA"

    Returns: 9

  57. "ABBBBBBAABBBBBBBABABA"

    Returns: 14

  58. "AAAAAAABAAAAABAAAAAAAAAAAABAAAAAAAAAAABAA"

    Returns: 23

  59. "AAAAAA"

    Returns: 4

  60. "AAABAAA"

    Returns: 5

  61. "BAAAAAAAAAAA"

    Returns: 8

  62. "AAABBB"

    Returns: 6

  63. "ABABAABBBBBAABABBABBABABABBBAABBABA"

    Returns: 31

  64. "AABB"

    Returns: 4

  65. "AAAABB"

    Returns: 4

  66. "ABAAB"

    Returns: 4

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: