LeetCode Entry

2038. Remove Colored Pieces if Both Neighbors are the Same Color

2.10.2023 medium 2023 kotlin

Is A wins in middle-removing AAA or BBB game

2038. Remove Colored Pieces if Both Neighbors are the Same Color medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/357

Problem TLDR

Is A wins in middle-removing AAA or BBB game

Intuition

We quickly observe, that removing A in BBAAABB doesn’t make B turn possible, so the outcome does not depend on how exactly positions are removed. A can win if it’s possible game turns are more than B. So, the problem is to find how many consequent A’s and B’s are.

Approach

We can count A and B in a single pass, however, let’s write a two-pass one-liner using window Kotlin method.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), can be O(1) if asSequence used

Code


    fun winnerOfGame(colors: String) = with(colors.windowed(3)) {
      count { it.all { it == 'A' } } > count { it.all { it == 'B' } }
    }