Problem Statement | |||||||||||||
Many elections are decided by plurality voting, which means that the winning candidate is the one who earns more votes than any other candidate. Such elections are susceptible to the phenomenon of vote splitting. Several candidates with similar views may draw support from the same voting base, thereby losing to a single candidate who holds less popular views. One remedy for vote splitting is a runoff election, where the field of candidates is narrowed down through successive rounds of voting until one candidate wins a majority of the vote. The scheme known as instant runoff voting, or IRV, is intended to accomplish the same result as a runoff election without incurring the expense of multiple voting rounds. In an IRV election, each voter uses a slip of paper called a ballot to rank the slate of n candidates from 1 to n. The ballots are tallied as follows. 1. If one candidate is ranked first on more than half of all ballots, this candidate is declared the winner. 2. Otherwise, the candidate with the fewest number-one rankings is eliminated from all ballots, and each voter's ranking is adjusted as necessary. If a voter ranked this candidate first, for instance, the number-one rank on her ballot is now reallocated to her second-ranked candidate, and so on down the line. If several candidates are tied for fewest number-one rankings, all of them are eliminated in this fashion. 3. If no candidates remain, the election is declared void. Otherwise, return to step 1. For an election with n candidates, you are given a String containing n distinct upper-case letters, each of which represents a candidate. You are also given a String[] encoding all ballots cast by the voting public. Each ballot ranks the candidates from most favored to least favored. If n is 5, for example, the candidates might be encoded as "PQRST", and some voter may rank them on her ballot as "SRTQP", signifying that she ranks candidate S first and candidate P fifth. Tally the ballots as described above to determine the outcome of the election. If the election is void, return an empty String. Otherwise, return a single-character String containing the candidate's code. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
| - | candidates contains between 1 and 10 characters, inclusive | ||||||||||||
| - | each character in candidates is an upper-case letter between 'A' and 'Z', inclusive | ||||||||||||
| - | candidates contains no duplicate characters | ||||||||||||
| - | ballots contains between 1 and 50 elements, inclusive | ||||||||||||
| - | each element of ballots is exactly as long as candidates | ||||||||||||
| - | each element of ballots contains the same characters as candidates, without duplication, but not necessarily in the same order | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||