LC301 - Remove Invalid Parentheses

Problem

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example

Example 1:

Input: s = "()())()"

Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"

Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("

Output: [""]

Constraints:

• 1 <= s.length <= 25

• s consists of lowercase English letters and parentheses '(' and ')'.

• There will be at most 20 parentheses in s.

Solution

Use a BFS to explore removal of every parenthesis from the string. If the resulting string is valid, add to result set. Use a set to keep track of visited strings to avoid redundancy. Once a valid string is found, exit the loop as it is guaranteed to have the minimum number. Complexity is T(O(2^n)), S(O(2^n)).

bool isValid(const string &s) {
	int parity = 0;
	for (auto c : s) {
		if (c == '(') parity++;
		else if (c ==')') parity--;
		if (parity < 0) return false;
	}
	return parity == 0;
}

vector<string> removeInvalidParentheses(string s) {
	queue<pair<string, int>> q;
	unordered_set<string> visited;
	unordered_set<string> results;
	
	q.push({s, 0});
	visited.insert(s);

	while (!q.empty()) {
		auto size = q.size();

		for (auto i = 0; i < size; i++) {
			auto [current, start] = q.front();
			q.pop();

			if (isValid(current)) {
				results.insert(current);
				}

			for (auto j = start; j < current.size(); j++) {
				if (current[j] != '(' && current[j] != ')') continue;
				auto next = current.substr(0, j) + current.substr(j + 1);
				if (!visited.count(next)) {
					q.push({next, j});
					visited.insert(next);	
				}
			}
		}
		if (!results.empty()) break;
	}
	return vector<string>(results.begin(), results.end());
}