1366. Rank Teams by Votes

package Leetcode.Array;

import java.util.Arrays;

/**
 * @author zhengxingxing
 * @date 2024/12/29
 */
public class RankTeamsByVotes {
    public static String rankTeams(String[] votes) {
        // Handle edge cases: empty input or null
        if(votes == null || votes.length == 0){
            return "";
        }

        // If there's only one vote, return it directly
        if (votes.length == 1){
            return votes[0];
        }

        // Create a 2D array to store vote counts
        // First dimension [26]: represents teams (A-Z)
        // Second dimension [26]: represents positions (0 to 25)
        // count[team][position] stores how many votes a team got for that position
        int[][] count = new int[26][26];

        // Array to track which teams participated in voting
        // teams[i] will be true if team (A+i) received any votes
        boolean[] teams = new boolean[26];
        int teamCount = 0;

        /* First Important Section: Vote Counting Loop
         * Outer loop: Iterates through each vote (ballot)
         * Inner loop: Processes each position in the current vote
         *
         * For example, if vote is "ABC":
         * - First iteration (i=0): Increment count for A in position 0
         * - Second iteration (i=1): Increment count for B in position 1
         * - Third iteration (i=2): Increment count for C in position 2
         *
         * Also marks teams as participating when they first appear
         */
        for (String vote : votes) {
            for (int i = 0; i < vote.length(); i++) {
                int team = vote.charAt(i) - 'A';  // Convert character to 0-25 index
                count[team][i]++;                 // Increment vote count for team at position i
                if (!teams[team]) {               // If this is first time seeing this team
                    teams[team] = true;           // Mark team as participating
                    teamCount++;                  // Increment total number of teams
                }
            }
        }

        // Create array to store participating teams as characters
        Character[] result = new Character[teamCount];
        int index = 0;
        for (int i = 0; i < 26; i++) {
            if (teams[i]) {
                result[index++] = (char)('A' + i);
            }
        }

        /* Second Important Section: Custom Sorting Logic
         * This comparator implements the ranking rules:
         * 1. Primary Rule: Teams are ranked by votes at each position, starting from position 0
         * 2. Secondary Rule: If teams tie in all positions, sort alphabetically
         *
         * For example, comparing teams A and B:
         * - First checks votes in position 0
         * - If tied, checks position 1
         * - If tied, checks position 2
         * - If tied in all positions, compares team names (A vs B)
         *
         * The subtraction (count[teamB][i] - count[teamA][i]) ensures:
         * - Positive result: teamB ranks higher (has more votes)
         * - Negative result: teamA ranks higher
         * - Zero: tied at this position, continue checking
         */
        Arrays.sort(result, (a, b) -> {
            int teamA = a - 'A';
            int teamB = b - 'A';

            // Compare votes at each position
            for (int i = 0; i < 26; i++) {
                if (count[teamA][i] != count[teamB][i]) {
                    return count[teamB][i] - count[teamA][i];  // Higher votes first
                }
            }
            // If all positions are tied, sort alphabetically
            return a - b;
        });

        // Convert result array to string
        StringBuilder sb = new StringBuilder();
        for (char c : result) {
            sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        // Test case 1: Multiple votes with clear preference
        String[] votes1 = {"ABC","ACB","ABC","ACB","ACB"};
        System.out.println("Test case 1:");
        System.out.println("Input: " + Arrays.toString(votes1));
        System.out.println("Output: " + rankTeams(votes1));
        System.out.println("Expected: ACB");

        // Test case 2: Minimal votes with different preferences
        String[] votes2 = {"WXYZ","XYZW"};
        System.out.println("\nTest case 2:");
        System.out.println("Input: " + Arrays.toString(votes2));
        System.out.println("Output: " + rankTeams(votes2));
        System.out.println("Expected: XWYZ");

        // Test case 3: Single vote with all letters
        String[] votes3 = {"ZMNAGUEDSJYLBOPHRQICWFXTVK"};
        System.out.println("\nTest case 3:");
        System.out.println("Input: " + Arrays.toString(votes3));
        System.out.println("Output: " + rankTeams(votes3));
        System.out.println("Expected: ZMNAGUEDSJYLBOPHRQICWFXTVK");
    }
}