LeetCode Entry

1758. Minimum Changes To Make Alternating Binary String

24.12.2023 easy 2023 kotlin

In a stressfull situation better to just use 4 counters: oddOnes, evenOnes, oddZeros, evenZeros. Then do something with them.

1758. Minimum Changes To Make Alternating Binary String easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/449

TLDR

Minimum operations to make 01-string with no two adjacent equal

Intuition

There are only two possible final variations - odd zeros even ones or even zeros odd ones. We can count how many positions to changes for each of them, then return smallest counter.

Approach

In a stressfull situation better to just use 4 counters: oddOnes, evenOnes, oddZeros, evenZeros. Then do something with them.

Complexity

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

  • Space complexity: \(O(1)\)

Code


  fun minOperations(s: String): Int {
    var oddOnesEvenZeros = 0
    var oddZerosEvenOnes = 0
    for (i in s.indices) when {
      s[i] == '0' && i % 2 == 0 -> oddZerosEvenOnes++
      s[i] == '0' && i % 2 != 0 -> oddOnesEvenZeros++
      s[i] == '1' && i % 2 == 0 -> oddOnesEvenZeros++
      s[i] == '1' && i % 2 != 0 -> oddZerosEvenOnes++
    }
    return min(oddOnesEvenZeros, oddZerosEvenOnes)
  }