Оптимизация кода подсчета подстрок

Дана строка S из 2 6 N 6 200000 круглых скобок. Посчитайте количество подстрок S[i..j], 1 6 i < j 6 N, которые являются правильными скобочными выражениями. Скобочное выражение является правильным, если выполняются два условия: (i) при чтении слева направо количество закрывающих скобок никогда не превышает количество открывающих скобок; и (ii) во всем выражении количество открывающих и закрывающих скобок совпадает. Например, в строке S = ()(()) есть 4 подходящие подстроки:

Формат входных данных Строка из 2 6 N 6 200000 круглых скобок. Формат выходных данных Неотрицательное целое число

Мой код:

s = input()
s = [1 if i == '(' else -1 for i in list(s)]
cheked = set()
ans = 0
L = len(s)
for l in range(L+1 if L % 2 else L, 1, -2):
    for i in range(L-l+1):
        if (i, i+l-1) in cheked:
            continue
        sum = 0
        end = None
        for j in range(i, i+l):
            sum += s[j]
            if sum < 0:
                break
            if sum == 0:
                cheked.add((i, j))
                if end:
                    cheked.add((end+1, j))
                end = j

print(len(cheked))