Simple Java solution w/ Explanation


  • 0

    The idea is to have two arrays nextRound and eliminate.
    nextRound keeps track of number of elements in D/R who are still valid for the nextRound
    eliminate keeps track of number of future candidates of D/R who are already eliminated by previous members.

    As we walk through the string, we build a new string that contains all the selected senators for nextRound, and in the end of the round, we reset the nextround, but carry over the eliminate array, as the counts in this array are still valid for the nextround.

    As we walk through each element in the string:

    1. If am already eliminated based on the values in the eliminate array, reduce the elimination count and proceed without adding myself to the next round.
    2. If am not eliminated, then I include myself in the nextRound, and chose to increase the elimination count of the other party.
    public static String predictPartyVictory(String senate) {
            HashMap<Character, Integer> map = new HashMap<>();
            map.put('D', 0);
            map.put('R', 1);
            int[] nextRound = new int[2], eliminate = new int[2];
            while(true) {
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < senate.length(); i++) {
                    if (eliminate[map.get(senate.charAt(i))] > 0) {
                        eliminate[map.get(senate.charAt(i))]--;
                    } else {
                        nextRound[map.get(senate.charAt(i))]++;
                        eliminate[map.get(senate.charAt(i)) ^ 1]++;
                        sb.append(senate.charAt(i));
                    }
                }
    
                if (nextRound[0] - eliminate[0] > 0 && nextRound[1] - eliminate[1] > 0) {
                    nextRound = new int[2];
                    senate = sb.toString();
                } else {
                    return nextRound[0] - eliminate[0] > 0 ? "Dire" : "Radiant";
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.