Reversing characters of string of parenthesis to achieve at max H string depth

Question

Given a integer H and string s which contains only ( and ) characters, and is properly formed (every opening bracket has corresponding closing bracket, the pairs of brackets are properly nested), return an integer indicating minimally how many brackets you need to reverse to achieve valid string which depth is no more than H.

The depth of string in this case is the maximum level of brackets nesting. For example, string (()(())) has depth equal to 3.

Generally, I think we can apply greedy approach - just iterate over string characters and while this process maintain a variable that stores current depth of string. If at any moment it's going to be higher than H, reverse current bracket. Also, in the case when depth is going to be below zero, also reverse the character.

That's code I've written, and it works perfectly fine:

#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;
}

That was my intuition. But I can't figure out how can I be sure that the final string (after reversing specific characters) will always be valid (parenthess are nested properly etc).

Firstly, at some point, we will come to the case where depth is going to exceed H. This is where we reverse the opening bracket into closing bracket. Assume we did it on index i (while iterating over s). Due to this modification, we will have closing bracket that has no corresponding bracket in future (some index j where j > i). It may happen that depth is below zero after this (so we reverse closing bracket to opening), but it's not necessary (and we will end up with invalid string).

That's where my reasoning ends. For me, it seems invalid, but if the code works, it means I missed something.

So, how can I be sure, that after performing these all operations, I will end up with valid string?

Answer 1

To rephrase the question, I think you are asking for a proof regarding the correctness of your program as opposed to "write a fuzzer" as some comments suggested.

You can think about a valid bracket string this way: For your brack string s of length n, we can represent it using a sequence a. Let a_i = +1 if the i-th character is (, and let a_i = -1 if the i-th character is ). Now that s is a valid bracket sequence if and only if ∑ _i=0 ^k a_i ≥ 0 for 0 ≤ k < n and that ∑ _i=0 ^n-1 a_i = 0. (See Catalan Number and Dywk path for more details.)

Thus, changing a ( to a ) is equivalent to changing a +1 to a -1. Therefore, suppose you change a_l = +1 to a_l = -1 (( to )), and a_m = -1 to a_m = +1 () to () for some l < m, then ∑ _i=0 ^k a_i would be unchanged for all k before l and after m. As for the sums between l and m, since your program is essentially looking for the first m where the sum ∑ _i=0 ^m a_i becomes negative after you changed ( to ) at l, they are certainly not negative. Therefore, the bracket string produced by your program is always valid.

As for your concern "due to this modification, we will have closing bracket that has no corresponding bracket in future" and "it may happen that depth is below zero after this", this would actually not be an issue. Consider the following example:

( ( ( ) ( ) ) )

Your solution should flip the bold brackets if I want the maximum depth to be 2.

( ( ) ) ( ) ( )

Now note the bold brackets below, previously this is a bracket pair: ( ( ( ) ( ) ) )

But the left most bracket would now pair like this:

( ( ) ) ( ) ( )

Therefore, you needn't worry about what brackets are paired exactly, but just that every closing bracket is paired with some opening bracket.