解释

我们将逐个字符处理输入的字符串，并更新有关到目前为止遇到的括号的某些信息。对于每种支架类型，创建一个堆栈，用于保留未补偿的开放支架的位置。基本上，它表示在检查时需要多少个当前类型的右括号才能使字符串有效。

对于输入的每个括号，请执行下列操作之一：

1. 如果支架是开口支架（任何类型），只需将其位置添加到相应的堆栈中即可。
2. 否则，它是一个结束括号。如果堆栈中没有左括号，只需增加结果总和 - 可以立即补偿不平衡的右括号。
3. 最后，它是一个右括号，在当前类型的堆栈中有左括号。因此，将位于相同类型的最后一个左括号和当前括号之间的其他类型的所有不平衡括号的数量相加！不要忘记从堆栈中删除匹配的元素。

最后，将每个堆栈的剩余大小添加到生成的总和中，因为每种类型的左括号可能仍然存在不平衡。

法典

我在 C++ 中创建了一个简单的解决方案，但如果需要，它可以很容易地转换为任何其他语言：

#include <iostream>
#include <stack>
#include <unordered_map>

bool isOpeningBracket(char bracket) {
    return bracket == '(' || bracket == '[' || bracket == '{';
}

int main() {
    std::string line;
    std::cin >> line;
    std::unordered_map<char, char> closingToOpeningBracket = {
            {')', '('},
            {']', '['},
            {'}', '{'}
    };

    std::unordered_map<char, std::unique_ptr<std::stack<uint64_t>>> bracketsMap;
    bracketsMap['{'] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['['] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['('] = std::make_unique<std::stack<uint64_t>>();
    uint64_t addOperations = 0;

    for(auto i = 0; i < line.size(); i++) {
        auto bracket = line[i];
        bool isOpening = isOpeningBracket(bracket);

        auto key = bracket;
        if (!isOpening) {
            key = closingToOpeningBracket[bracket];
        }
        auto &bracketStack = bracketsMap[key];
        if (isOpening) {
            bracketStack->push(i);
        } else if (!bracketStack->empty()) {
            auto openingBracketPosition = bracketStack->top();
            bracketStack->pop();

            for (auto & [key, value] : bracketsMap) {
                while (!value->empty() && value->top() > openingBracketPosition) {
                    addOperations++;
                    value->pop();
                }
            }
        } else {
            addOperations++;
        }
    }

    for (auto & [key, value] : bracketsMap) {
        addOperations += value->size();
    }

    std::cout << addOperations << "\n";

    return 0;
}

时间和空间复杂性

该解的时间和空间复杂度为 O（n）。

贪婪地想想，对于每个结束标签，都必须有一个开始标签，如果不是这样，那么我们必须添加一个开始括号。

因此，我们可以通过遍历字符串并保留左括号的计数来找到最小加法。因此，当我们遇到左括号时，我们会增加计数变量，当我们遇到右括号时，如果我们有一些正数，我们会减少计数变量，否则，如果计数为零，则意味着我们必须在此处添加一个左括号。下面是这种贪婪方法的代码。时间复杂度 O（n） 和空间复杂度 O（1）。

int minAddToMakeValid(string s) {
    int cnt1  = 0 , cnt2 = 0, cnt3 = 0,  ans = 0;
    for(char ch : s){
        if(ch == '(')cnt1++;
        else if(ch == ')'){
            if(cnt1==0)ans++;
            else cnt1--;
        }
        if(ch == '{')cnt2++;
        else if(ch == '}'){
            if(cnt2==0)ans++;
            else cnt2--;
        }
        if(ch == '[')cnt3++;
        else if(ch == ']'){
            if(cnt3==0)ans++;
            else cnt3--;
        }
    }
    return ans + cnt1 + cnt2 + cnt3;
}

您可以使用动态编程及时执行此操作（对于任意数量的支架类型）。这不是运行时的下限，但贪婪的方法似乎不适用于此问题。O(n^3)

首先，对于任何括号字符串，了解“平衡的最小添加量”与“平衡的最小删除量”相同是有帮助的，因为删除框架更易于使用。要了解为什么会这样，请考虑一组最小的添加：对于现在匹配但之前不匹配的每个括号，我们也可以删除该括号，反之亦然。

这个想法是计算所有可能的括号对：创建一个所有索引的列表，其中 和 是相同类型的开括号和闭括号对。然后，我们找到我们可以拥有的最大间隔数，使得任何两个间隔要么是嵌套的，要么是不相交的。这正是需要平衡的要求，如果你好奇的话，这意味着我们正在寻找由我们的区间形成的交集图的最大大小的简单完美子图。[i, j], 0 <= i < j < ns[i]s[j][i, j]

有间隔，因此对这种方法的任何修改都有一个下限。我们对这些间隔进行排序（按开始排序，如果并列，则按结束排序），并使用动态规划 （DP） 来查找我们可以拥有的嵌套或不相交间隔的最大数量。O(n^2)O(n^2)

我们的 DP 方程有 3 个参数：左、右和min_index。 是我们被允许使用的索引的包容性范围，并且是我们允许使用的最小索引（在我们的区间列表中）区间。如果我们知道我们可以实际使用的最左边的区间，比如说，答案将来自使用或不使用这个区间。如果我们不使用它，我们会得到.如果我们确实使用间隔，我们将可以嵌套在其中的最大间隔数相加，加上严格从 .这是。[left, right]smin_index[start, end]dp(left, right, min_index+1)(start, end)end1 + dp(start+1, end-1, min_index+1) + dp(end+1, right, min_index+1)

如需更完整的定义：

dp(left, right, min_index) := 
maximum number of intervals from interval_list[min_index:]
that are contained in [left, right] and all pairwise nested or disjoint.

Also, let 
first_index := max(smallest index of an interval starting at or after left,
                  min_index)
so that interval_list[first_index] = (first_start, first_end).


dp(left, right, min_index) = 0 if (left > right or first_index >= length(interval_list)),

                             max(dp(left, right, first_index+1),
                                 1
                                 + dp(first_start+1, first_end-1, first_index+1)
                                 + dp(first_end+1, right, first_index+1))

                                 otherwise.

---

下面是该算法的 Python 实现：

def balance_multi_string(s: str) -> int:
    """Given a multi-paren string s, return minimum deletions to balance
       it. 'Balanced' means all parentheses are matched, and
       all pairs from different types are either nested or disjoint
       Runs in O(n^3) time.
    """

    open_brackets = {'{', '[', '('}
    closed_brackets = {'}', ']', ')'}
    bracket_partners = {'{': '}', '[': ']', '(': ')',
                        '}': '{', ']': '[', ')': '('}
    
    n = len(s)

    bracket_type_to_open_locations = collections.defaultdict(list)

    intervals = []

    for i, x in enumerate(s):
        if x in closed_brackets:
            for j in bracket_type_to_open_locations[bracket_partners[x]]:
                intervals.append((j, i))
        else:
            bracket_type_to_open_locations[x].append(i)

    if len(intervals) == 0:
        return n

    intervals.sort()
    num_intervals = len(intervals)

    @functools.lru_cache(None)
    def point_to_first_interval_strictly_after(point: int) -> int:
        """Given a point, return index of first interval starting
        strictly after, or num_intervals if there is none."""
        if point > intervals[-1][0]:
            return num_intervals
        if point < intervals[0][0]:
            return 0
        return bisect.bisect_right(intervals, (point, n + 2))

    @functools.lru_cache(None)
    def dp(left: int, right: int, min_index: int) -> int:
        """Given inclusive range [left,right], and minimum interval index,
        return the maximum number of intervals we can add
        within this range so that all added intervals
        are either nested or disjoint."""
        if left >= right or min_index >= num_intervals:
            return 0
        starting_idx = max(point_to_first_interval_strictly_after(left - 1), min_index)
        if starting_idx == num_intervals or intervals[starting_idx][0] >= right:
            return 0
        first_start, first_end = intervals[starting_idx]
        best_answer = dp(first_start, right, starting_idx + 1)  # Without first interval

        if first_end <= right:  # If we include the first interval
            best_answer = max(best_answer,
                              1
                              + dp(first_start + 1, first_end - 1, starting_idx + 1)
                              + dp(first_end + 1, right, starting_idx + 1))
        return best_answer

    return n - 2 * dp(0, n - 1, 0)

例子：

( [ ( [ ) } ]     -->   3

} ( } [ ) [ { }   -->   4

} ( } } ) ] ) {   -->   6

{ ) { ) { [ } }   -->   4

) ] } { } [ ( {   -->   6

] ) } } ( [ } {   -->   8