Leetcode daily # 4.05.2023

[649. Dota2 Senate]

4.05.2023

649. Dota2 Senate medium

fun predictPartyVictory(senate: String): String {
    val queue = ArrayDeque<Char>()
        senate.forEach { queue.add(it) }
        var banR = 0
        var banD = 0
        while (true) {
            var haveR = false
            var haveD = false
            repeat(queue.size) {
                val c = queue.poll()
                if (c == 'R') {
                    haveR = true
                    if (banR > 0) banR--
                    else {
                        queue.add(c)
                        banD++
                    }
                } else {
                    haveD = true
                    if (banD > 0) banD--
                    else {
                        queue.add(c)
                        banR++
                    }
                }
            }
            if (!haveR) return "Dire"
            if (!haveD) return "Radiant"
        }
    }

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/202

Intuition

One can ban on any length to the right.
We can just simulate the process, and it will take at most two rounds.

Approach

Use Queue and count how many bans are from the Radiant and from the Dire.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)