Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1366.html
1366. Rank Teams by Votes
Level
Medium
Description
In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.
The ordering of teams is decided by who received the most positionone votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.
Given an array of strings votes
which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.
Return a string of all teams sorted by the ranking system.
Example 1:
Input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
Output: “ACB”
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.
Example 2:
Input: votes = [“WXYZ”,”XYZW”]
Output: “XWYZ”
Explanation: X is the winner due to tiebreaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn’t have any votes as second position.
Example 3:
Input: votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
Output: “ZMNAGUEDSJYLBOPHRQICWFXTVK”
Explanation: Only one voter so his votes are used for the ranking.
Example 4:
Input: votes = [“BCA”,”CAB”,”CBA”,”ABC”,”ACB”,”BAC”]
Output: “ABC”
Explanation: Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.
Example 5:
Input: votes = [“M”,”M”,”M”,”M”]
Output: “M”
Explanation: Only team M in the competition so it has the first rank.
Constraints:
1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length
for0 <= i, j < votes.length
.votes[i][j]
is an English uppercase letter. All characters of
votes[i]
are unique.  All the characters that occur in
votes[0]
also occur invotes[j]
where1 <= j < votes.length
.
Solution
The number of teams teams
is the length of any string in votes
. Since there are 26 different uppercase letters, create a 2D array votesCount
with 26 rows and teams + 1
columns. Each column i
from 0 to teams  1
represents the number of votes at rank i
(0based) for each team, and the last column stores the original order (in alphabetical order).
For each vote
in votes
, loop over vote
and for each letter c
at index i
, the row number in votesCount
is c  'A'
, and increase votesCount[c  'A'][i]
by 1.
Then sort votesCount
according to the first teams
columns in descending order and according to the last column in ascending order.
Finally, obtain the first teams
rows’ team letters in votesCount
, arrange them in the order of the sorted array, and return.

class Solution { public String rankTeams(String[] votes) { int teams = votes[0].length(); int[][] votesCount = new int[26][teams + 1]; for (int i = 0; i < 26; i++) votesCount[i][teams] = i; for (String vote : votes) { for (int i = 0; i < teams; i++) { char c = vote.charAt(i); votesCount[c  'A'][i]++; } } Arrays.sort(votesCount, new Comparator<int[]>() { public int compare(int[] voteCount1, int[] voteCount2) { for (int i = 0; i < teams; i++) { if (voteCount1[i] != voteCount2[i]) return voteCount2[i]  voteCount1[i]; } return voteCount1[teams]  voteCount2[teams]; } }); StringBuffer sb = new StringBuffer(); for (int i = 0; i < teams; i++) { char team = (char) ('A' + votesCount[i][teams]); sb.append(team); } return sb.toString(); } }

class Solution: def rankTeams(self, votes: List[str]) > str: n = len(votes[0]) cnt = defaultdict(lambda: [0] * n) for vote in votes: for i, c in enumerate(vote): cnt[c][i] += 1 return "".join(sorted(votes[0], key=lambda x: (cnt[x], ord(x)), reverse=True))

class Solution { public: string rankTeams(vector<string>& votes) { int n = votes[0].size(); int cnt[26][n]; memset(cnt, 0, sizeof cnt); for (auto& vote : votes) { for (int i = 0; i < n; ++i) { cnt[vote[i]  'A'][i]++; } } string ans = votes[0]; sort(ans.begin(), ans.end(), [&](auto& a, auto& b) { int i = a  'A', j = b  'A'; for (int k = 0; k < n; ++k) { if (cnt[i][k] != cnt[j][k]) { return cnt[i][k] > cnt[j][k]; } } return a < b; }); return ans; } };

func rankTeams(votes []string) string { cnt := [26][26]int{} for _, vote := range votes { for i, c := range vote { cnt[c'A'][i]++ } } ans := []byte(votes[0]) sort.Slice(ans, func(i, j int) bool { cnt1, cnt2 := cnt[ans[i]'A'], cnt[ans[j]'A'] for k, a := range cnt1 { b := cnt2[k] if a != b { return a > b } } return ans[i] < ans[j] }) return string(ans) }