# A 13-Line C# DP Solution

• ``````public int LongestValidParentheses(string s) {
int[] pair = new int[s.Length];
int result = 0;
for(int i = s.Length - 2; i >= 0; i--){
if(s[i] == '('){
if(s[i + 1] == ')') pair[i] = 2;
else if(pair[i + 1] != 0 && i + pair[i + 1] + 1 < s.Length && s[i + pair[i + 1] + 1] == ')')
pair[i] = pair[i + 1] + 2;
if(pair[i] != 0 && i + pair[i] < s.Length && pair[i + pair[i]] != 0)
pair[i] += pair[i + pair[i]];
}
result = Math.Max(result, pair[i]);
}
return result;
}
``````

Below is another problem and almost has nothing to do with the longest valid parenthesis.
I pasted here for looking up.

``````//remove minimum number of left and right brackets and return the string with
//valid bracket pairs.
//given (a))()), should return (a)(), or(a());
//given )()()), should return either()() or(());
//given()((9()), should return either ()(9()) or()((9)).
private static IList<string> validParenthesis(string s){
ISet<string> result = new HashSet<string>();
if (s.Length == 0) return result.ToList();
int i = 0, j = s.Length - 1;
while (s[i] == ')') i++; while (s[j] == '(') j--;
s = s.Substring(i, j - i + 1);
if (s.Length == 0) return result.ToList();
StringBuilder sb = new StringBuilder();
for (i = 0; i < s.Length; i++) //1. find the removing subsequence
if (s[i] == '(') sb.Append(s[i]);
else if (s[i] == ')'){
if (sb.Length == 0 || sb[sb.Length - 1] == ')')
sb.Append(s[i]);
else sb.Length -= 1;
}
dfs(result, "", s, 0, sb.ToString(), 0, new Stack<char>()); //2. DFS to get all results
return result.ToList();
}

private static void dfs(ISet<string> result, string curStr, string s, int curIndex, string toBeRemoved, int curRemove, Stack<char> valid){
if(curRemove == toBeRemoved.Length){
if (valid.Count == 0){
Stack<char> stack = new Stack<char>();
string str = s.Substring(curIndex);
for (int i = 0; i < str.Length; i++)
if (str[i] != '(' && str[i] != ')') continue;
else if (str[i] == '(') stack.Push('(');
else if (stack.Count == 0) return;
else if (str[i] == ')') stack.Pop();
if (stack.Count == 0) result.Add(curStr + str);
}
return;
}
if (curIndex == s.Length) return;
if(s[curIndex] == toBeRemoved[curRemove])
dfs(result, curStr, s, curIndex + 1, toBeRemoved, curRemove + 1, valid);
if (s[curIndex] == '('){
valid.Push('(');
dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
valid.Pop();
}
else if(s[curIndex] == ')'){
if(valid.Count == 0) return;
else{
valid.Pop();
dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
valid.Push('(');
}
}
else dfs(result, curStr + s[curIndex], s, curIndex + 1, toBeRemoved, curRemove, valid);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.