CSES - Bittijärjestäminen Annettuna on merkkijono, jonka jokainen merkki on 0 tai 1. Saat jokaisella siirrolla vaihtaa kaksi vierekkäistä merkkiä keskenään, ja tehtäväsi on siirtää kaikki 0-merkit ennen 1-merkkejä. Mikä on pienin määrä siirtoja?

Esimerkiksi merkkijonossa 101010 tarvitaan ainakin $6$ siirtoa. Tässä on yksi optimaalinen ratkaisu:

101010 $\rightarrow$ 101001 $\rightarrow$ 011001 $\rightarrow$ 010101 $\rightarrow$ 001101 $\rightarrow$ 001011 $\rightarrow$ 000111

Voit olettaa, että merkkijonossa on enintään $10^5$ merkkiä. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Python

Toteuta tiedostoon bitsort.py funktio solve, joka antaa pienimmän siirtojen määrän.
def solve(s):
    # TODO

if __name__ == "__main__":
    print(solve("000100")) # 2
    print(solve("111000")) # 9
    print(solve("101010")) # 6
Java

Toteuta tiedostoon BitSort.java metodi solve, joka antaa pienimmän siirtojen määrän.
public class BitSort {
    public long solve(String s) {
        // TODO
    }

    public static void main(String[] args) {
        BitSort b = new BitSort();
        System.out.println(b.solve("000100")); // 2
        System.out.println(b.solve("111000")); // 9
        System.out.println(b.solve("101010")); // 6
    }
}