Solution Notes (Kalki Seksaria):

We can define the depth of the string up to some position as opening paranthseses minus closing parentheses. There are two cases:

Case 1: A ')' should be made into a '('. If the depth becomes negative, we must convert any closing parenthesis at or before this location to an opening one.

Case 2: A '(' should be made into a ')'. This occurs if the depth at the end of the string is positive. In order to correct this, we must convert an opening parenthesis into a closing one. However, we must be careful and avoid making the depth negative at any point. In order to ensure that we do not make the depth negative, the parenthesis that we replace must be after any points at which the depth is less than 2. If the original depth at a point is 0 or 1, the new depth at that point will be negative after the exchange, as the depth decreases by two.

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

in >> s;
int ans = 0;
int depth = 0;
int closingSeen = 0; //since start of string
int openingSeen = 0; //since last time with depth = 1

for (int i = 0; i < s.size(); i++)
{
if(s[i] == '(')
{
depth++;
openingSeen++;
}
else
{
depth--;
closingSeen++;
}

if(depth <= 1)
openingSeen = 0;
if(depth == -1)
{
ans = closingSeen;
break;
}
}

if(depth > 0)
ans = openingSeen;

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