Swift Stack
From what I can see, most of the parenthesis problems can be solved using Stack.\n\n*1. Maintain invalid indices that shouldn\'t be included in the final result
From what I can see, most of the parenthesis problems can be solved using Stack.\n\n****1. Maintain invalid indices that shouldn\'t be included in the final result****\nThe idea is to maintain a `stack` consisting of indices of `(` and `invalidIndices` set donating the indices we shouldn\'t include in the final result. \n* Iterate over every index `i` of the input string, we have to handle **3 cases**:\n\t* If `arr[i] == "("`, append `i` to `stack`\n\t* If `arr[i] == ")"`, there are **2 sub-cases**:\n\t\t* If `stack is empty` --> `i` is an invalid index --> insert into `invalidIndices`\n\t\t* If `stack is not empty` --> `i` can make a balanced pair with any index inside `stack` --> remove the last element from `stack`\n\t* If `arr[i] is other character`, `i` is indeed a valid index --> don\'t need to do anything.\n* Every remaining index inside `stack` is invalid -->  insert all into `invalidIndices`\n* Finally, iterate over every index `i` again, if `i` doesn\'t exist in the `invalidIndices`, append `arr[i]` to the final result.\n```swift\nclass Solution {\n  func minRemoveToMakeValid(_ s: String) -> String {\n    let arr = Array(s)\n    let n = arr.count\n    \n    var invalidIndices = Set<Int>()\n    var stack = [Int]()\n    for i in 0..<n {\n      let c = arr[i]\n      switch c {\n        case "(": stack.append(i)\n        case ")":\n          if stack.isEmpty {\n            invalidIndices.insert(i)\n          } else {\n            stack.popLast()\n          }\n        default: break\n      }\n    }\n    \n    invalidIndices.formUnion(stack)\n    \n    var res = ""\n    for i in 0..<n where !invalidIndices.contains(i) {\n      res.append(arr[i])\n    }\n    \n    return res\n  }\n}\n// Time complexity: O(n) where n is length of s\n// Space complexity: O(n)\n```\n\n****2. Maintain valid indices that need to be included in the final result****\nAnother way is to maintain `validIndices` set donating the indices we must include in the final result. It requires some small tweaks from the approach #1 above.\n* Iterate over every index `i` of the input string, we have to handle **3 cases**:\n\t* If `arr[i] == "("`, append `i` to `stack`\n\t* If `arr[i] == ")"`, there are **2 sub-cases**:\n\t\t* If `stack is empty` --> `i` is an invalid index --> do nothing\n\t\t* If `stack is not empty` --> `i` can make a balanced pair with any index inside `stack` --> remove the last element from `stack` and insert it as well as `i` into `validIndices`\n\t* If `arr[i] is other character`, `i` is indeed a valid index --> insert into `validIndices`\n* Finally, iterate over every index `i` again, if `i` exists in the `validIndices`, append `arr[i]` to the final result.\n\nI find this approach is slightly better than approach #1, especially when `s` only contains `(`.\n```swift\nclass Solution {\n  func minRemoveToMakeValid(_ s: String) -> String {\n    let arr = Array(s)\n    let n = arr.count \n    \n    var validIndices = Set<Int>()\n    var stack = [Int]()\n    for i in 0..<n {\n      switch arr[i] {\n      case "(": stack.append(i)\n      case ")": \n        if let last = stack.popLast() {\n          validIndices.formUnion([last, i])\n        }\n      default: validIndices.insert(i)\n      }\n    }\n    \n    var res = ""\n    for i in 0..<n where validIndices.contains(i) {\n      res.append(arr[i])\n    }\n    \n    return res\n  }\n}\n// Time complexity: O(n) where n is length of s\n// Space complexity: O(n)\n```
['Stack', 'Swift']