Merkkijonon jokainen merkki on ( tai ). Joka siirrolla poistat merkkijonosta mahdollisimman vasemmalta osajonon (). Jatkat näin, kunnes mitään ei voi enää poistaa. Montako merkkiä jää jäljelle lopuksi?

Esimerkiksi kun merkkijono on ((())(, se muuttuu ensin muotoon (()( ja sitten muotoon ((. Tässä tapauksessa lopullisessa merkkijonossa on 2 merkkiä.

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

Python

Toteuta tiedostoon brackets.py funktio count, joka antaa merkkien määrän lopussa.

def count(s):
    # TODO
    
if __name__ == "__main__":
    print(count("(()())")) # 0
    print(count(")))))")) # 5
    print(count("((())(")) # 2
    print(count("(()()())()()")) # 0
    print(count("))))))((((((")) # 12

Java

Toteuta tiedostoon Brackets.java metodi count, joka antaa merkkien määrän lopussa.

public class Brackets {
    public int count(String s) {
        // TODO
    }

    public static void main(String[] args) {
        Brackets b = new Brackets();
        System.out.println(b.count("(()())")); // 0
        System.out.println(b.count(")))))")); // 5
        System.out.println(b.count("((())(")); // 2
        System.out.println(b.count("(()()())()()")); // 0
        System.out.println(b.count("))))))((((((")); // 12
    }
}