Interview Question - Remove Invalid Parentheses

remove_invalid_parentheses.py

# Interviwer asks: An expression will be given which can contain open and close parentheses and 
# optionally some characters, No other operator will be there in string. We need to remove the minimum number of
# parentheses to make the input string valid. If more than one valid output is possible removing the same number
# of parentheses, then print all such output possibilities.

def isvalid(s):
    ctr = 0
    for c in s:
        if c == '(':
            ctr += 1
        elif c == ')':
            ctr -= 1
            if ctr < 0:
                return False

    return ctr == 0

def removeInvalidParentheses(s):
    level = set([s])
    while True:
        valid = list(filter(isvalid, level))
        if valid:
            return valid
        # check validity of all possible substrings with one character removed.
        nextlevels = set()
        for s in level:
            for i in range(len(s)):
                nextlevels.add(s[:i] + s[i+1:])
        level = nextlevels

# Here are some test cases.
# test_string = ')()()('
# test_string = '(()))'
# test_string = ')('
# test_string = '()))(()'
# test_string = '(()())'

print(removeInvalidParentheses(')()()('))
print(removeInvalidParentheses('(()))'))
print(removeInvalidParentheses(')('))
print(removeInvalidParentheses('()))(()'))
print(removeInvalidParentheses('(()())'))