Tehtäväsi on laskea, monessako merkkijonon osajonossa ensimmäinen ja viimeinen merkki on sama. Esimerkiksi merkkijonossa ababca tällaiset osajonot ovat

• a (kolmesti)
• aba
• ababca
• abca
• b (kahdesti)
• bab
• c

eli yhteensä 10 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 bothsame.py funktio count, joka palauttaa halutun tuloksen.

def count(s):
    # TODO

if __name__ == "__main__":
    print(count("aaa")) # 6
    print(count("abcd")) # 4
    print(count("ababca")) # 10

Java

Toteuta tiedostoon BothSame.java metodi count, joka palauttaa halutun tuloksen.

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

    public static void main(String[] args) {
        BothSame b = new BothSame();
        System.out.println(b.count("aaa")); // 6
        System.out.println(b.count("abcd")); // 4
        System.out.println(b.count("ababca")); // 10
    }
}