# Very Easy To Understand - 5 ms - O(n) solution without Stack or DP

• for input example:

"()()))((()(())(()))((())(()()()()()()(((((())))))())()())()(())(())())))))(())()((((((((()()(())))))())())))()(((()())()))(((()()((((("

I scan the string forward and backward change the string to:

()()##((()(())(()))((())(()()()()()()(((((())))))())()())()(())(())())####(())()((((((((()()(())))))())())))()(((()())()))###()()#####

the invalid ( or ) are removed.

Then you count the longest valid substring length.

``````public class Solution {
public int longestValidParentheses(String s) {
char[] c = s.toCharArray();
int len = c.length, t = 0, ans = 0;
for (int i = 0, y = 0; i < len; i++)
if (c[i] == '(')
y++;
else if (c[i] == ')' && --y < 0) {
y = 0;
c[i] = '#';
}

for (int i = len - 1, y = 0; i >= 0; i--) {
if (c[i] == ')')
y++;
else if (c[i] == '(' && --y < 0) {
y = 0;
c[i] = '#';
}

t = (c[i] == '#') ? 0 : t + 1;
ans = Math.max(ans, t);
}
System.out.println(new String(c));

return ans;
}
}``````

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