最长有效的括号字符子序列

class Solution {
public:
    int maxscore;
    int length;
    int n;
    unordered_set<string> hash;
    //左括号是1分 右括号 是-1分 合规的字符串一定时是0
    void dfs(string s, int score,string buf,int l,int r,int index){
        //如果出现删过头或者分数出现负数或者超过最大数返回
        if(l<0||r<0||score<0||score>maxscore)
            return;
        if(l==0&&r==0&&buf.length()==length)
            hash.insert(buf);
        if(index==n)
            return;

        char ch = s[index];
        if(ch=='('){
            dfs(s, score + 1, buf + '(', l, r, index + 1);//选择添加（括号 则+1分 继续遍历
            dfs(s, score, buf, l - 1, r, index + 1);//选择不添加左括号相当于删除左括号 则分数不变 继续遍历
        }
        else if(ch==')'){
            dfs(s, score - 1, buf + ')', l, r, index + 1);//选择添加）括号 则-1分 继续遍历
            dfs(s, score, buf, l, r - 1, index+1);//选择不添加右括号相当于删除右括号 则分数不变 继续遍历
        }else{
            dfs(s, score, buf + ch, l, r, index + 1);//遇到其他字符 直接添加 继续遍历
        }
    }

        vector<string> maxValidParenthesesStr(string s){
            //合规的字符串 分数一定是0
            //分数一定不会超过maxscore，maxscore就是所有可匹配的(都在左边，一直+1，能达到的最大分数
            maxscore = 0;
            n = s.size();
            int left = 0;
            int right = 0;
            int l = 0, r = 0;
            length = 0;
            for(auto&ch:s){
                if(ch=='('){
                    //统计左括号的数量
                    //需要删除的左括号的数量
                    l++;
                    left++;
                }
                else if(ch==')'){
                    //统计右括号数量
                    if(l!=0)
                        l--;//遇到可能匹配的右括号
                    else
                        r++;//需要删除的右括号的数量
                    right++;
                }
            }
            length = n - l - r;//字符串中除了左括号和右括号以外的应该有的长度
            maxscore = left < right ? left : right;//最大分数为可匹配的左括号或右括号的数量
            dfs(s, 0, "", l, r, 0);
            return {hash.begin(), hash.end()};
        }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
   private List<String> res3 = new ArrayList<String>();

	public String[] maxValidParenthesesStr(String s) {
		int lremove = 0;
		int rremove = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				lremove++;
			} else if (s.charAt(i) == ')') {
				if (lremove == 0) {
					rremove++;
				} else {
					lremove--;
				}
			}
		}
		helper(s, 0, lremove, rremove);
		String[] strings = new String[res3.size()];
		return res3.toArray(strings);
	}

	private void helper(String str, int start, int lremove, int rremove) {
		if (lremove == 0 && rremove == 0) {
			if (isValid2(str)) {
				res3.add(str);
			}
			return;
		}

		for (int i = start; i < str.length(); i++) {
			if (i != start && str.charAt(i) == str.charAt(i - 1)) {
				continue;
			}
			// 如果剩余的字符无法满足去掉的数量要求，直接返回
			if (lremove + rremove > str.length() - i) {
				return;
			}
			// 尝试去掉一个左括号
			if (lremove > 0 && str.charAt(i) == '(') {
				helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
			}
			// 尝试去掉一个右括号
			if (rremove > 0 && str.charAt(i) == ')') {
				helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
			}
		}
	}

	//判断是否为有效的括号对
	private boolean isValid2(String str) {
		int cnt = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				cnt++;
			} else if (str.charAt(i) == ')') {
				cnt--;
				if (cnt < 0) {
					return false;
				}
			}
		}
		return cnt == 0;
	}
}