Problem 1758 (Dec 24)

(Last updated: )

Question statement:

You are given a string $\texttt{s}$ consisting only of the characters ‘0’ and ‘1’. In one operation, you can change any ‘0’ to ‘1’ or vice versa. The string is called alternating if no two adjacent characters are equal. For example, the string “010” is alternating, while the string “0100” is not. Return the minimum number of operations needed to make $\texttt{s}$ alternating.

Solution:

Main idea:

  • There are exactly two alternating binary strings $b_1$ and $b_2$ of the same length as $\texttt{s}$, namely $0101\dots$ and $1010\dots$.
  • Recall bit-wise xor $\oplus$ (^ operator in python) is defined such that $1 \oplus 1=0 \oplus 0=0$ and $1 \oplus 0 = 0 \oplus 1 = 1$.
  • $b_1\oplus s$ and $b_2\oplus s$ both return a binary number that has $1$s in places where $s$ differs from $b_1$ and $b_2$ respectively.
  • Return the minimum number of $1$s that appear among the two outputs.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minOperations(self, s: str) -> int:
    if(len(s)%2 == 0):
        sym1 = '10'*int((len(s)/2))
        sym2 = '01'*int((len(s)/2))
    else:
        sym1 = '10'*int((len(s)//2))+'1'
        sym2 = '01'*int((len(s)//2))+'0'
    r1 = 0
    r2 = 0
    
    for i in range(len(s)):
        if(int(s[i])^int(sym1[i]) == 1):
            r1+=1
        if(int(s[i])^int(sym2[i]) == 1):
            r2+=1
    return min(r1, r2)


Comments:

Time complexity: O(n)

At the time of submission, the above solution passes leetcode submission cases in 79ms, beats 5.11% of users. It uses 17.4MB of memory, beating 51.45% of users.