难度: Medium
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」(A) 的字符串，其中 A 是一个有效的「括号字符串」示例 1：
输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de" 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：
输入：s = "a)b(c)d" 输出："ab(c)d"
示例 3：
输入：s = "))(("
输出：""
解释：空字符串也是有效的
提示：
1 <= s.length <= 105s[i] 可能是 '('、')' 或英文小写字母运行时间: 50 ms
内存: 17.5 MB
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = []
s = list(s)
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
elif s[i] == ")":
if stack:
stack.pop()
else:
s[i] = ""
while stack:
s[stack.pop()] = ""
return "".join(s)
此题解通过利用栈结构来跟踪并处理字符串中的括号。首先，将字符串转换为字符数组，以便能够修改特定索引的字符。遍历字符数组时，遇到'('时将其索引入栈，表示一个潜在的未匹配左括号。遇到')'时，检查栈是否为空：如果不为空，表示栈顶的'('可以与之匹配，于是将其出栈；如果为空，说明当前的')'无法匹配，将其位置上的字符设为空字符串。遍历完成后，栈中剩余的都是未能匹配的'('的索引，将这些位置上的字符同样设为空字符串。最后，将修改后的字符数组重新组合成字符串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stack = [] # 用于存放未匹配的'('的索引
s = list(s) # 将字符串转换为字符数组，方便修改
for i in range(len(s)):
if s[i] == '(':
stack.append(i) # 遇到'('，入栈
elif s[i] == ')':
if stack:
stack.pop() # 遇到')'且栈非空，出栈一个'('
else:
s[i] = '' # 栈为空，说明')'无法匹配，删除之
while stack:
s[stack.pop()] = '' # 清理所有未匹配的'('
return ''.join(s) # 重新组合成字符串
是的，当代码遇到无法匹配的')'时，将其设为空字符串确实意味着这个字符在最终的字符串中会完全消失。这是因为将字符设为空字符串相当于在数组中删除该字符，而最后使用''.join(s)时，这些空字符串将不会被包括在内，从而在结果字符串中不再出现这些无效的括号。
算法中使用一个栈来存储每个'('字符的索引。当遇到一个')'字符时，如果栈不为空，则从栈中弹出一个元素，这表示找到了一个匹配的括号对。如果遍历结束后栈仍有元素，这些元素即为未匹配的'('的索引。通过遍历栈并将这些索引对应的字符在字符数组中设为空字符串，这样可以确保这些未匹配的'('在最终字符串中被删除。
是的，此算法也考虑了输入字符串中只含有小写字母而不含任何括号的情况。在这种情况下，由于字符串中不存在括号，栈操作（入栈和出栈）将不会发生，字符数组也不会进行任何修改。因此，最终通过''.join(s)返回的结果将是原始输入字符串本身，未发生任何改变。