Merkkijonon jokainen merkki on joko A, B tai C. Joka siirrolla saat vaihtaa kahden merkin (ei välttämättä vierekkäisen) paikkaa keskenään. Mikä on pienin määrä siirtoja, joka tarvitaan järjestämään merkkijono?

Esimerkiksi kun merkkijono on CBACBA, siirtoja tarvitaan vähintään 3. Tässä on optimaalinen ratkaisu:

CBACBA \rightarrow ABACBC \rightarrow AABCBC \rightarrow AABBCC

Voit olettaa, että merkkijonossa on enintään 10^5 merkkiä.

Python

Toteuta tiedostoon abcstring.py metodi solve, joka antaa pienimmän siirtojen määrän.

def solve(s):
    # TODO

if __name__ == "__main__":
    print(solve("CCAABB")) # 4
    print(solve("CBACBA")) # 3
    print(solve("AAAA")) # 0

Java

Toteuta tiedostoon ABCString.java metodi solve, joka antaa pienimmän siirtojen määrän.

public class ABCString {
    public int solve(String s) {
        // TODO
    }

    public static void main(String[] args) {
        ABCString a = new ABCString();
        System.out.println(a.solve("CCAABB")); // 4
        System.out.println(a.solve("CBACBA")); // 3
        System.out.println(a.solve("AAAA")); // 0
    }
}