1249. Minimum Remove to Make Valid Parentheses

题目信息

题号:

1249

难度:

Medium

主题:

字符串、括号匹配、栈

原题:

LeetCode 1249

重点:

只能删除括号字符,使剩余括号序列有效并最小化删除数量;普通小写字母必须保留

题目重述

给定由小写英文字母、左括号和右括号组成的字符串 s。可以删除任意括号字符,但不能改变剩余字符的相对顺序。

请删除最少数量的括号,使结果中的括号正确匹配,并返回任意一个满足最少删除次数的结果字符串。

1 <= s.length <= 10^5,s 只包含小写英文字母和 (、)。

自建示例

删除两端无法匹配的括号:

输入:s = "a)b(c)d("
输出:"ab(c)d"
解释:删除下标 1 的多余右括号和末尾无法闭合的左括号后,剩余括号有效。

原字符串有效时无需删除:

输入:s = "((x))"
输出:"((x))"
解释:所有括号都已正确匹配,最少删除数量为零。