LeetCode Entry

649. Dota2 Senate

4.05.2023 medium 2023 kotlin

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

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 substack

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)\)