How to solve a modified version of Leetcode Valid Parentheses?

I’d try the following:

Let f(i, j) represent the least removals for substring S[i..j]
  where i < j
  and S[j] is some closing parenthetical

Then f(i, j) =
  0 if i > j
  1 + f(i, j - 1) if S[j] has no matching
    opening at or after S[i]
  Otherwise min(
      f(k + 1, j - 1)
      + f(i, k - 1)
    )
    where k ≥ i
      and S[k] is a matching opening parenthetical for S[j]

If the number of brackets to remove is expected to be small relative to the input size, then a breadth-first search might be an efficient approach.

Here is an implementation in Python so it can be compared with other answers that provided Python code:

def solve(brackets):
    n = len(brackets)
    # The queue represents nodes on one level in the BFS search tree.
    #   It has tuples of (stack, index), where the stack is a linked list
    #   of used indices (having opening brackets), and the index is the next
    #   unprocessed character from the input.
    queue = [ (None, 0) ]
    num_removals = 0
    while queue: # BFS loop
        next_queue = []
        # Iterate all relevant possibilities to 
        #    remove numRemovals brackets before index i
        for stack, i in queue:
            # Perform stack operations starting at character index i:
            while i < n:
                if brackets[i] in "[{(":
                    stack = (stack, i)  # push on stack
                elif stack and brackets[stack[1]] + brackets[i] in ("()","{}","[]"):
                    stack = stack[0]  # pop from stack
                else:
                    break
                i += 1
            else:
                if not stack:
                    return num_removals  # BINGO!
            # We have an opening/closing pair that is not of the same type, 
            #   like "(" and "]". Two options for what to remove:
            if stack:
                next_queue.append( (stack[0], i) )  # discard the opening bracket
            if i < len(brackets):
                next_queue.append( (stack, i + 1) )  # discard the closing bracket
        queue = next_queue
        num_removals += 1

Here is the same in a JavaScript snippet where you can interactively input your brackets:

function solve(brackets) {
    let queue = [ [null, 0] ];
    let numRemovals = 0;
    while (queue.length) { // BFS loop
        const nextQueue = [];
        for (let [stackTop, i] of queue) {
            while (true) {
                if ("[{(".includes(brackets[i])) {
                    stackTop = [stackTop, i]; // push on stack
                } else if (stackTop && ["()","{}","[]"]
                           .includes(brackets[stackTop[1]] + brackets[i])) {
                    stackTop = stackTop[0]; // pop from stack
                } else break;
                i++;
            }
            if (!stackTop && i >= brackets.length) return numRemovals;
            if (stackTop) nextQueue.push([stackTop[0], i]);
            if (i < brackets.length) nextQueue.push([stackTop, i + 1]);
        }
        queue = nextQueue;
        numRemovals++;
    }
}

// I/O management
const [input, output] = document.querySelectorAll("input, span");
input.addEventListener("input", refresh);
function refresh() {
    const brackets = input.value.replace(/[^(){}\[]]/g, ""); // clean input
    const count = solve(brackets);
    output.textContent = count;
}
refresh();

Brackets: <input value="[(])"><br>
Is valid after removal of <span>0</span> brackets. 

This is the algorithm

def min_removals_to_make_valid(s):
    stack = []
    invalid_count = 0
    pair = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if stack and stack[-1] == pair[ch]:
                stack.pop()
            else:
                invalid_count += 1  # unmatched or mistyped closing bracket

    return invalid_count + len(stack)

This solution uses DFS with memoization (functools.lru_cache in python) to explore all possible ways to remove brackets and find the minimum number of removals to make the string valid.

You know there are 2 behaviors for each character - one is removing and next will be keeping.

In the case of keeping a bracket, we only proceed when it maintains valid structure.

• We can push opening brackets into a simulated stack.

• We can pop only if the closing ticket matches the last opening. (fully matched and no need to remove)

DFS is based on recursive methods, and this will track the index and current stack of unmatched bracket openings.

And finally, result is the minimal total of removed characters needed to balance the string.

from functools import lru_cache

def min_removals_to_make_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    opens = set(pairs.values())
    closes = set(pairs.keys())

    @lru_cache(None)
    def dfs(i, stack):
        if i == len(s):
            return len(stack)  # unclosed open brackets

        ch = s[i]
        min_remove = float('inf')

        # Option 1: Remove ch
        min_remove = min(min_remove, 1 + dfs(i + 1, stack))

        # Option 2: Keep ch
        if ch in opens:
            min_remove = min(min_remove, dfs(i + 1, stack + (ch,)))
        elif ch in closes:
            if stack and stack[-1] == pairs[ch]:
                min_remove = min(min_remove, dfs(i + 1, stack[:-1]))
        else:
            # not a bracket
            min_remove = min(min_remove, dfs(i + 1, stack))

        return min_remove

    return dfs(0, ())

#- "([)]" should return 2
# - "([{}])" should return 0
# - "([]])" should return 1
input = "([]])"
print(min_removals_to_make_valid(input))