反转括号字符串的字符以实现最大 H 字符串深度

Question

给定一个整数

H

和字符串

s

，其中仅包含

(

和

)

字符，并且格式正确（每个左括号都有相应的右括号，括号对正确嵌套），返回一个整数指示最少需要反转多少个括号才能获得深度不超过

H

的有效字符串。

本例中字符串的深度是括号嵌套的最大层数。例如，字符串

(()(()))

的深度等于 3。

一般来说，我认为我们可以应用贪婪方法 - 只需迭代字符串字符，同时此过程维护一个存储当前字符串深度的变量。如果在任何时候它会高于

H

，则反转当前括号。另外，在深度低于零的情况下，也要反转字符。

这是我写的代码，它运行得很好：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, H;
    cin >> n >> H;

    string s;
    cin >> s;

    int depth = 0;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(' && depth == H) {
            s[i] = ')';
            ++ans;
        }
        else if (s[i] == ')' && depth == 0) {
            s[i] = '(';
            ++ans;
        }

        if (s[i] == '(')
            ++depth;
        else
            --depth;
    }

    cout << ans;
}

这是我的直觉。但我不知道如何确定最终字符串（反转特定字符后）始终有效（括号正确嵌套等）。

首先，在某个时刻，我们会遇到深度将超过

H

的情况。这是我们将左括号反转为右括号的地方。假设我们在索引

i

上执行此操作（同时迭代

s

）。由于这一修改，我们将来将拥有没有相应括号的结束括号（某些索引

j

其中

j > i

）。此后深度可能会低于零（因此我们将右括号反转为左括号），但这不是必需的（并且我们最终会得到无效的字符串）。

我的推理到此结束。对我来说，这似乎无效，但如果代码有效，则意味着我错过了一些东西。

那么，我如何确定在执行所有这些操作后，我最终会得到有效的字符串？

Answer 1

为了重新表述这个问题，我认为您要求提供有关程序正确性的证明，而不是像一些评论建议的那样“编写模糊器”。

您可以这样考虑有效的括号字符串：对于长度为

n

的括号字符串 s，我们可以使用序列 a 来表示它。如果第 i 个字符是 _{(，则令 a}i = +1；如果第 i 个字符是 _{)，则令 a}i = -1 。现在

s

是一个有效的括号序列当且仅当 Σ _i=0 ^k a_i ≥ 0 对于 0 ≤ k < n 并且 Σ _i=0 ^n-1 a_i = 0。（有关更多详细信息，请参阅 Catalan Number 和 Dywk 路径。）

因此，将

(

更改为

)

相当于将 +1 更改为 -1。因此，假设您将 a_l = +1 更改为 a_l = -1（

(

更改为

)

），并且 a_m = -1到 a_m = +1（

)

到

(

）对于一些 l < m，则 Σ _i=0 ^k a_{i对于 l} 之前和 m 之后的所有 k， 都不会改变。至于 l 和 m 之间的总和，因为您的程序本质上是在寻找第一个 m，其中总和 Σ _i=0 ^m a_i 变为当您在

l

将

(

更改为 ) 后，它们肯定不是负数。因此，您的程序生成的括号字符串始终有效。

至于您担心的“由于这次修改，我们将来会有没有相应括号的结束括号”和“此后深度可能会低于零”，这实际上不是问题。考虑以下示例：

( ( ( ) ( ) ) )

如果我希望最大深度为 2，你的解决方案应该翻转 bold 括号。

( ( ) ) ( ) ( )

现在请注意下面的粗体括号，之前这是一对括号： ( ( ( ) ( ) ) )

但是最左边的括号现在会像这样配对：

( ( ) ) ( ) ( )

因此，您不必担心哪些括号精确配对，只需担心每个右括号与某个左括号配对即可。