CSES - Bittijono

Annettuna on merkkijono, jossa jokainen merkki on 0 tai 1. Tehtäväsi on muuttaa osa biteistä vastakkaisiksi niin, että muutosten jälkeen missään kohdassa ei ole vierekkäin kahta samaa bittiä. Mikä on pienin määrä muutoksia?

Esimerkiksi merkkijonossa 10010001 tarvitaan vähintään kolme muutosta. Optimaalinen ratkaisu on muuttaa kohdissa 0, 1 ja 5 olevat bitit, jolloin tuloksena on merkkijono 01010101.

Voit olettaa, että merkkijonon pituus on enintään 10^5.

Python

Toteuta tiedostoon bitstring.py funktio calculate, joka ilmoittaa pienimmän muutosten määrän.

def calculate(s):
    # TODO

if __name__ == "__main__":
    print(calculate("1010")) # 0
    print(calculate("1111")) # 2
    print(calculate("10010001")) # 3

Java

Toteuta tiedostoon BitString.java metodi calculate, joka ilmoittaa pienimmän muutosten määrän.

public class BitString {
    public int calculate(String s) {
        // TODO
    }

    public static void main(String[] args) {
        BitString b = new BitString();
        System.out.println(b.calculate("1010")); // 0
        System.out.println(b.calculate("1111")); // 2
        System.out.println(b.calculate("10010001")); // 3
    }
}