Remove Invalid Parentheses (BFS)

To solve the Remove Invalid Parentheses problem using BFS, I would first validate a helper function to check if a string has balanced parentheses. The core strategy involves treating every possible string modification as a node in a graph. We start with the initial string in our queue. In each iteration, we process the entire current level of the queue. For every string in this level, we generate all possible next states by removing exactly one parenthesis character. Before adding these new states to the queue, we check if they are valid. If we find any valid strings during this level, we collect them all and immediately terminate the search, ensuring we have removed the minimum number of parentheses. This level-by-level approach guarantees optimality. Crucially, I would use a hash set to track visited strings. Without this, the algorithm could enter an infinite loop or waste time re-processing the same invalid string via different deletion paths. For example, given '()())()', removing the first ')' or the second ')' leads to the same intermediate state. By tracking visited nodes, we ensure efficiency. Finally, we return the list of unique valid strings found at the first successful level. This approach balances finding all solutions with strict adherence to the minimum removal constraint.