Problem

In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one 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.

You are 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 teamssorted by the ranking system.

Examples

Example 1

1
2
3
4
5
6
7

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 ranked third by 3 voters.
Team C was ranked second by 3 voters and 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

1
2
3
4

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.

Example 3

1
2
3

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter, so their votes are used for the ranking.

Constraints

  • 1 <= votes.length <= 1000
  • 1 <= votes[i].length <= 26
  • votes[i].length == votes[j].length for 0 <= 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 in votes[j] where 1 <= j < votes.length.

Solution

Method 1 – Counting and Custom Sorting

Intuition

The main idea is to count how many times each team appears in each rank position, then sort the teams by comparing their counts for each position, breaking ties alphabetically.

Approach

  1. For each team, create an array to count how many times it appears in each rank position.
  2. Iterate through all votes and update the counts for each team and position.
  3. Sort the teams using a custom comparator:
    • For two teams, compare their counts for each position from highest to lowest.
    • If all counts are equal, break ties by alphabetical order.
  4. Join the sorted teams into a string and return.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes[0].size();
        unordered_map<char, vector<int>> cnt;
        for (char c : votes[0]) cnt[c] = vector<int>(n);
        for (auto& v : votes)
            for (int i = 0; i < n; ++i)
                cnt[v[i]][i]++;
        vector<char> teams(votes[0].begin(), votes[0].end());
        sort(teams.begin(), teams.end(), [&](char a, char b) {
            for (int i = 0; i < n; ++i)
                if (cnt[a][i] != cnt[b][i])
                    return cnt[a][i] > cnt[b][i];
            return a < b;
        });
        return string(teams.begin(), teams.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func rankTeams(votes []string) string {
    n := len(votes[0])
    cnt := map[byte][]int{}
    for i := 0; i < n; i++ {
        cnt[votes[0][i]] = make([]int, n)
    }
    for _, v := range votes {
        for i := 0; i < n; i++ {
            cnt[v[i]][i]++
        }
    }
    teams := []byte(votes[0])
    sort.Slice(teams, func(i, j int) bool {
        for k := 0; k < n; k++ {
            if cnt[teams[i]][k] != cnt[teams[j]][k] {
                return cnt[teams[i]][k] > cnt[teams[j]][k]
            }
        }
        return teams[i] < teams[j]
    })
    return string(teams)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String rankTeams(String[] votes) {
        int n = votes[0].length();
        Map<Character, int[]> cnt = new HashMap<>();
        for (char c : votes[0].toCharArray()) cnt.put(c, new int[n]);
        for (String v : votes)
            for (int i = 0; i < n; ++i)
                cnt.get(v.charAt(i))[i]++;
        List<Character> teams = new ArrayList<>();
        for (char c : votes[0].toCharArray()) teams.add(c);
        teams.sort((a, b) -> {
            for (int i = 0; i < n; ++i)
                if (cnt.get(a)[i] != cnt.get(b)[i])
                    return cnt.get(b)[i] - cnt.get(a)[i];
            return a - b;
        });
        StringBuilder sb = new StringBuilder();
        for (char c : teams) sb.append(c);
        return sb.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun rankTeams(votes: Array<String>): String {
        val n = votes[0].length
        val cnt = mutableMapOf<Char, IntArray>()
        for (c in votes[0]) cnt[c] = IntArray(n)
        for (v in votes)
            for (i in v.indices)
                cnt[v[i]]!![i]++
        val teams = votes[0].toList()
        return teams.sortedWith(Comparator { a, b ->
            for (i in 0 until n) {
                if (cnt[a]!![i] != cnt[b]!![i])
                    return@Comparator cnt[b]!![i] - cnt[a]!![i]
            }
            a - b
        }).joinToString("")
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        cnt = {c: [0]*n for c in votes[0]}
        for v in votes:
            for i, c in enumerate(v):
                cnt[c][i] += 1
        teams = list(votes[0])
        teams.sort(key=lambda x: ([-cnt[x][i] for i in range(n)], x))
        return ''.join(teams)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn rank_teams(votes: Vec<String>) -> String {
        let n = votes[0].len();
        let mut cnt = std::collections::HashMap::new();
        for c in votes[0].chars() {
            cnt.insert(c, vec![0; n]);
        }
        for v in &votes {
            for (i, c) in v.chars().enumerate() {
                cnt.get_mut(&c).unwrap()[i] += 1;
            }
        }
        let mut teams: Vec<char> = votes[0].chars().collect();
        teams.sort_by(|&a, &b| {
            for i in 0..n {
                if cnt[&a][i] != cnt[&b][i] {
                    return cnt[&b][i].cmp(&cnt[&a][i]);
                }
            }
            a.cmp(&b)
        });
        teams.into_iter().collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    rankTeams(votes: string[]): string {
        const n = votes[0].length;
        const cnt: Record<string, number[]> = {};
        for (const c of votes[0]) cnt[c] = Array(n).fill(0);
        for (const v of votes)
            for (let i = 0; i < n; ++i)
                cnt[v[i]][i]++;
        const teams = votes[0].split('');
        teams.sort((a, b) => {
            for (let i = 0; i < n; ++i)
                if (cnt[a][i] !== cnt[b][i])
                    return cnt[b][i] - cnt[a][i];
            return a < b ? -1 : 1;
        });
        return teams.join('');
    }
}

Complexity

  • ⏰ Time complexity: O(T * N + N^2 log N), where T is the number of votes and N is the number of teams. Counting is O(T*N), sorting is O(N^2 log N) due to custom comparator.
  • 🧺 Space complexity: O(N^2), for storing the counts for each team and position.