我们给了一个仅包含(,),{,},[,]字符的字符串。目的是找到此类字符串的最大长度,以便通过交换相邻字符或删除字符来使其平衡。我们将通过比较相邻的字符来做到这一点,如果它们彼此相对,则可以互换它们。(} {,)(,] [可以交换,而{{,)),[[,}},)),]]]]]不可以交换)。
同样,如果一个字符没有匹配对,那么也可以将其删除。(“ {{}] [”,这里第一个{可以删除,并且平衡的字符串长度变为4)
str[]= “ {{{}}{]]][()” length 12
输出结果
Maximum length of balances string: 8
说明-无法交换str [0]和str [1],删除str [0] =“ {{}} {]]] [()”原始str [1]和str [2]无法交换,删除str [1] =“ {}} {]]] [()” {}是平衡的} {可以交换,删除下一个2]],交换] [和()也平衡最终字符串为{} {} [] ()。长度为8。
str[]= “(((((()” length 7
输出结果
str[]= “(((((()” length 7
说明-仅平衡str [5]和str [6],将其全部删除。最终字符串()。长度是2
字符数组str []存储原始字符串。整数长度存储字符串的长度。
函数maxBalancedStr(char str [],int len)将字符串及其长度作为参数,并返回平衡字符串的最大长度。
变量count用于存储此类字符串的长度,最初为0。
从第一个字符开始遍历字符串,并检查是否可以交换相邻字符以使两个字符平衡。或者,如果它们已经平衡,则将计数增加2。
对(),)(和{},} {和[],] [这样的货币对执行此操作,如果存在这样的货币对,也要递增i,以移至下一个字符。
最后,计数存储平衡字符串的长度。
返回计数作为结果。
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the length of // the longest balanced sub-string int maxBalancedStr(char str[20], int len){ int count=0; // Traversing the string for (int i = 0; i <len;i++) { // Check type of parentheses and // incrementing count for it if((str[i]=='(' && str[i+1]==')') || (str[i]==')' && str[i+1]=='(')) //can swap{ count+=2; ++i; } else if((str[i]=='{' && str[i+1]=='}') || (str[i]=='}' && str[i+1]=='{')) //can swap{ count+=2; ++i; } else if((str[i]=='[' && str[i+1]==']') || (str[i]==']' && str[i+1]=='[')) //can swap count+=2; ++i; } } return count; } // Driven code int main(){ char str[] = ")([]](("; int length=7; cout << maxBalancedStr(str,length); return 0; }
输出结果
4