Java recursive solution, beat 95%

• First of all, the best strategy for everyone is to ban the opponent senator just next to himself.

Notice that at any given point during the iteration, we can know that which side is leading and how many they lead (meaning that following opponents will be banned). So we store this info in a variable `banD`. For example, `banD == 2` means that 2 following D senators will be banned and `banD == -2` means that 2 following R senators will be banned.

Then the recursive method simulates a real voting process. If a senator is not banned, we leave it to the next round. And keep the leading information among rounds.

``````class Solution {
int banD = 0;
public String predictPartyVictory(String senate) {
StringBuilder sb = new StringBuilder();
int countR = 0;
for (int i = 0; i < senate.length(); i++) {
if (senate.charAt(i) == 'R') {
if (banD >= 0) {
sb.append('R');
countR++;
}
banD++;
} else {
if (banD <= 0)
sb.append('D');
banD--;
}
}
if (countR == 0)
return "Dire";
if (countR == sb.length())