DENSE Editorial

editorial
, ,
21

Why my solution is leading to TLE although I am only traversing in O(n)…

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    int i = 0, j = n - 1;

    while (i < n && s[i] != '(')
    {
        i++;
    }

    while (i < j && j >= 0 && s[j] != ')')
    {
        j--;
    }

    // cout << i << " " << j << "\n";

    if (!(i < n && j >= 0 && i < j && (s[i] == '(' && s[j] == ')')))
    {
        cout << n << "\n";
        return;
    }
    else
    {
        string ans = "()";
        while (i < j && i < n && j >= 0)
        {
            i++;
            j--;

            if (i >= j)
            {
                break;
            }

            while (i < n && s[i] != '(')
            {
                i++;
            }

            while (j >= 0 && s[j] != ')')
            {
                j--;
            }

            if (!(i < j && (s[i] == '(' && s[j] == ')')))
            {
                break;
            }
            else
            {
                ans = "(" + ans + ")";
            }
        }
        cout << n - ans.size() << "\n";
    }
}