Java/C++ Stack
Intuition\nTo make the string valid with minimum removals, we need to get rid of all parentheses that do not have a matching pair.\n\n1. Push char index into th
#### Intuition\nTo make the string valid with minimum removals, we need to get rid of all parentheses that do not have a matching pair.\n\n1. Push char index into the stack when we see `\'(\'`.\n\n2. Pop from the stack when we see `\')\'`.\n\n\t- If the stack is empty, then we have `\')\'` without the pair, and it needs to be removed.\n\n3. In the end, the stack will contain indexes of `\'(\'` without the pair, if any. We need to remove all of them too. \n\n**Update:** check out the new approach 2 that collects indexes of all mismatched parentheses, and removes them right-to-left.\n\n#### Approach 1: Stack and Placeholder\n\nWe mark removed parentheses with `\'*\'`, and erase all of them in the end.\n\n**Java**\n```Java\npublic String minRemoveToMakeValid(String s) {\n  StringBuilder sb = new StringBuilder(s);\n  Stack<Integer> st = new Stack<>();\n  for (int i = 0; i < sb.length(); ++i) {\n    if (sb.charAt(i) == \'(\') st.add(i);\n    if (sb.charAt(i) == \')\') {\n      if (!st.empty()) st.pop();\n      else sb.setCharAt(i, \'*\');\n    }\n  }\n  while (!st.empty())\n    sb.setCharAt(st.pop(), \'*\');\n  return sb.toString().replaceAll("\\\\*", "");\n}\n```\n**C++**\n```CPP\nstring minRemoveToMakeValid(string s) {\n  stack<int> st;\n  for (auto i = 0; i < s.size(); ++i) {\n    if (s[i] == \'(\') st.push(i);\n    if (s[i] == \')\') {\n      if (!st.empty()) st.pop();\n      else s[i] = \'*\';\n    }\n  }\n  while (!st.empty()) {\n    s[st.top()] = \'*\';\n    st.pop();\n  }\n  s.erase(remove(s.begin(), s.end(), \'*\'), s.end());\n  return s;\n}\n```\n#### Approach 2: Stack with Tracking\n\nInstead of using placeholders, we can track indexes of all mismatched parentheses, and erase them in the end going right-to-left. This idea was inspired by [dibdidib](https://leetcode.com/dibdidib/).\n\nWe can introduce another stack to collect indexes of mismatched `\')\'`, or we can use the same stack and mark mismatched `\')\'` somehow. Here, we just negate the index to indicate `\')\'`.\n\n> Note that I am adding `1` to make the index `1`-based. You cannot tell if zero is negated :)\n\n**Java**\n```Java\npublic String minRemoveToMakeValid(String s) {\n  StringBuilder sb = new StringBuilder(s);\n  Stack<Integer> st = new Stack();\n  for (int i = 0; i < sb.length(); ++i) {\n    if (sb.charAt(i) == \'(\') st.add(i + 1);\n    if (sb.charAt(i) == \')\') {\n      if (!st.empty() && st.peek() >= 0) st.pop();\n      else st.add(-(i + 1));\n    }\n  }\n  while (!st.empty())\n    sb.deleteCharAt(Math.abs(st.pop()) - 1);\n  return sb.toString();\n}\n```\nIf we want to optimize for the worst-case scenario, we should avoid `deleteCharAt` inside the loop. Instead, we can copy characters that do not appear in the stack into another string builder. Since characters in the stack are naturally sorted, we can use two-pointer technique to do it in the linear time.\n> Note that for the OJ test cases, the runtime of this solution is a bit worse than for `deleteCharAt`.\n```\npublic String minRemoveToMakeValid(String s) {\n  StringBuilder sb = new StringBuilder(s), sb1 = new StringBuilder();\n  Stack<Integer> st = new Stack();\n  for (int i = 0; i < sb.length(); ++i) {\n    if (sb.charAt(i) == \'(\') st.add(i + 1);\n    if (sb.charAt(i) == \')\') {\n      if (!st.empty() && st.peek() >= 0) st.pop();\n      else st.add(-(i + 1));\n    }\n  }\n  for(int i = 0, j = 0; i < sb.length(); ++i) {\n      if (j >= st.size() || i != Math.abs(st.elementAt(j)) - 1) {\n        sb1.append(sb.charAt(i));\n      } else ++j;\n  }\n  return sb1.toString();\n}\n```\n**Complexity Analysis**\n- Time: O(n). We process each character once, or twice for \'single\' `\'(\'`.\n- Memory: O(n) for the stack.
[]