Stack⌗ 

class Solution {
public:
	string minRemoveToMakeValid(string s) {
		stack<char> st;
		char open = '(', close = ')';
		int open_count = 0;
		string res;

		// forward to remove unnecessary close parentheses
		for (auto iter = s.begin(); iter != s.end(); ++iter) {
			if (*iter == open) {
				open_count++;
			}
			if (open_count == 0 && *iter == close) {
				continue;
			}
			if (*iter == close) {
				open_count--;
			}
			st.push(*iter);
		}

		int close_count = 0;
		// backward to remove unnecessary open parentheses
		while (!st.empty()) {
			if (st.top() == close) {
				close_count++;
			}
			if (st.top() == open) {
				if (close_count == 0 ) {
					st.pop();
					continue;
				}
				close_count--;
			}

			res.push_back(st.top());
			st.pop();
		}

		reverse(res.begin(), res.end());
		return res;
	}
};