1
# ["ABC","ACB","ABC","ACB","ACB"]
2
# d = {
3
#    "A": [5, 0, 0],
4
#    "B": [0, 2, 3],
5
#    "C": [0, 3, 2]
6
# }
7
# keys represent the candidates
8
# index of array in dict represent the rank
9
# value of array item represent number of votes casted
10
# ref: https://www.programiz.com/python-programming/methods/built-in/sorted
11
class Solution:
12
    # T=O(mn + mlgm), S=O(mn)
13
    # n=number of votes
14
    # m=number of candidates and m(number of ranks) is constant(26)
15
    def rankTeams(self, votes: List[str]) -> str:
16
        d = {}
17
        # build the dict
18
        # T=O(mn), S=O(mn)
19
        # n=number of votes, m=number of candidates(26)
20
        for vote in votes:
21
            for i, c in enumerate(vote):
22
                # if key not in dict
23
                if c not in d:
24
                    # d[char] = [0, 0, 0]
25
                    d[c] = [0] * len(vote)
26
                # increment the count of votes for each rank
27
                # d["A"][0] = 1
28
                d[c][i] += 1
29
        # sort the dict keys in ascending order because if there is a tie we return in ascending order
30
        # sorted uses a stable sorting algorithm
31
        # T=O(mlgm), S=O(m)
32
        vote_names = sorted(d.keys())  # d.keys()=["A", "B", "C"]
33
        # sort the dict keys based on votes for each rank in descending order
34
        # T=O(mlgm), S=O(m)
35
        # sorted() always returns a list
36
        vote_rank = sorted(vote_names, reverse=True, key=lambda x: d[x])
37
        # join the list
38
        return "".join(vote_rank)