What's the Time Complexity and Space Complexity this function to check valid parenthesis?

Question

I am unable to find the Time Complexity and Space Complexity of the code to check valid parenthesis. Can anyone help, please?

code -

bool isValid(string s) 
{
        int s_size = s.length();
        for (int i = 0; i < s_size-1;i++)
        {
            if((s[i]=='(' && s[i+1]==')') || (s[i]=='[' && s[i+1]==']')|| (s[i]=='{' && s[i+1]=='}'))
            {
                s.erase(i, 2);
                i=-1;
                s_size-=2;
            }

        }
        if(s.empty())
            return true;
        else 
            return false;
                
    }

I think the space complexity is O(1) and the time complexity is O(n). Correct me please, if I am wrong.

Answer 1

For just the code snippet you posted above, the time complexity is O(n³).

As rightly pointed out by n. 'pronouns' m., the outer for loop for (int i = 0; i < s_size-1;i++) runs n² times because i resets to the starting point every time a match is found. And the s.erase() function also takes O(n) time to run. In total making up for a cubic O(n³) time complexity.

You can read up on std::string.erase() function here

You are right about space complexity. Its O(1).

To solve the above problem of Valid Parenthesis efficiently i.e., within O(n) time complexity and O(n) space complexity, consider using a stack.