More optimal solution Minimum Changes to Make Schedule Balanced

[edisonfreire]

https://github.com/codepath/compsci_guides/wiki/Minimum-Changes-to-Make-Schedule-Balanced

Better solution is understanding about stack but using a integer variable to simulate the stack because in this case we can have constant space complexity instead linear space complexity.

instead of stack we have variable to count how many open parentheses are left unpaired at the end and variable to count how many closing are left unpaired. loop through characters in the schedule if character is a opening parentheses, increment opening count if character is closing parentheses and opening count greater than 0, we decrement the opening parentheses count variable because we found a match else if character is a closing parentheses and opening count is 0, then we increment the closing parentheses count variable because there is impossible to have a pair with those closing parantheses

after looping through the schedule we return the unaccounted for opening parentheses count + unaccounted for closing parentheses count

def min_changes_to_make_balanced(schedule):
    open_with_no_closed = 0
    closed_with_no_open = 0
    for char in schedule:
        if char == '(':
            open_with_no_closed += 1  # new opening paranthese
        if char == ')' and open_with_no_closed > 0:
            # we found a corresponding closing paranthese to one of the opening
            open_with_no_closed -= 1
        elif char == ')' and open_with_no_closed == 0:  # closing paranthese with no possible opening
            closed_with_no_open += 1

    return open_with_no_closed + closed_with_no_open