CSES - ABC-merkkijono 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
    }
}