Solution Notes (Kalki Seksaria):

This problem can be solved by sweeping through the string. While sweeping, we can keep a count of the number of pairs of hind legs seen so far. For every pair of front legs that we see, Bessie can be located from any pair of hind legs that we have already seen to this pair of front legs. Due to this, we can add our count of the number of pairs of hind legs to our current answer. The total running time of this approach is only O(N). Note that the maximum input size is too large for the simple O(N^2) solution that explicitly checks every pair of positions in the string to run in time.

``````
#include <iostream>
#include <fstream>
using namespace std;
string s;
int main()
{
ifstream in ("cowfind.in");
ofstream out ("cowfind.out");

in >> s;
int ans = 0;
int backCount = 0;

for (int i = 1; i < s.size(); i++)
{
if(s[i-1] == ')' && s[i] == ')')
ans += backCount;
else if(s[i-1] == '(' && s[i] == '(')
backCount++;
}

out << ans << "\n";
out.close();
return 0;
}
``````