Tehtäväsi on laskea, monessako merkkijonon osajonossa on tasan kahta eri merkkiä. Esimerkiksi merkkijonossa aabacba tällaiset osajonot ovat

• aab
• aaba
• ab
• aba
• ac
• ba (kahdesti)
• cb

eli yhteensä $8$ osajonoa.

Voit olettaa, että merkkijono muodostuu merkeistä a–z ja siinä on enintään $10^5$ merkkiä. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.

Python

Toteuta tiedostoon twochar.py funktio count, joka ilmoittaa osajonojen määrän.

def count(s):
    # TODO

if __name__ == "__main__":
    print(count("aaaa")) # 0
    print(count("abab")) # 6
    print(count("aabacba")) # 8
    print(count("abacaadbaacaa")) # 21

Java

Toteuta tiedostoon TwoChar.java metodi count, joka ilmoittaa osajonojen määrän.

public class TwoChar {
    public long count(String s) {
        // TODO
    }

    public static void main(String[] args) {
        TwoChar t = new TwoChar();
        System.out.println(t.count("aaaa")); // 0
        System.out.println(t.count("abab")); // 6
        System.out.println(t.count("aabacba")); // 8
        System.out.println(t.count("abacaadbaacaa")); // 21
    }
}