In the Leetcode Longest Valid Parentheses problem solution Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
- 0 <= s.length <= 3 * 104
- s[i] is ‘(‘, or ‘)’.
Solution in C Programming
#define MAX(a,b) (((a)>(b))?(a):(b))
int longestValidParentheses(char * s){
char* start = s; // keep it to stop the backwards loop
char closer = ')'; // the sign that closes the substring. ) when we scan right and then ( when we go left
int longest = 0; // keeps the longest valid substring we saw
int length = 0; // length of current subtring we scan
int opened = 0; // the number of opened parentheses in the substring we scan
while ((*s != '\0') ) {
if (*s == closer) { // check the current char it either openes or closes a parentheses
opened--;
} else {
opened++;
}
if (opened < 0) { // the char closed a parentheses that wasn't open - this is the end of the current valid substring so nullify the counters
length = 0;
opened = 0;
} else {
if (*s == closer) { // another closed parentheses (in a valid substring) so add it to the length
length+=2;
}
if (opened == 0) { // end of closed unit of parentheses so keep it if it's the longest. but we keep counting as there maybe more units...
longest = MAX(longest,length);
}
}
if (closer == ')') {
// as long as we scan right
s++;
if (*s == '\0') { //finished scanning right - reverse direction!
closer = '(';
length = 0;
opened = 0;
s--;
}
} else {
// scan left
if (s==start) break; // back to where we started
s--;
}
}
return longest;
}Solution in C++ Programming
class Solution {
public:
int longestValidParentheses(string s) {
// Time complexity and space complexity = O(N)
if(s.empty()) return 0;
stack<int>mp;
mp.push(-1);
int cnt = 0;
int len = 0;
for(int i=0;i<s.length();i++){
if(s[i]=='(') mp.push(i);
else
{
mp.pop();
if(!mp.empty())
{
cnt = i-mp.top();
len = max(len,cnt);
}
else
mp.push(i);
}
}
return len;
//Time = O(N) and space = O(1)
int n = s.length();
int right = 0;
int left = 0;
len = 0;
for(int i=0;i<n;i++)
{
if(s[i]=='(') left++;
else right++;
if(left==right) len = max(len,2*right);
else if(left<right){
left = 0;
right = 0;
}
}
left = 0;
right = 0;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='(') left++;
else right++;
if(left==right) len = max(len,2*left);
if(left>right){
left = 0;
right = 0;
}
}
return len;
}
};Solution in Java Programming
class Solution {
public int longestValidParentheses(String s) {
char[] c = s.toCharArray();
int max= cal(c);
for(int i=0,j=c.length-1;i<=j;i++,j--){
char temp = c[i];
c[i]=c[j];
c[j]=temp;
}
for(int i=0;i<c.length;i++){
c[i]=(char)(c[i]^1);
}
return Math.max(max,cal(c));
}
public int cal(char[] c){
int res = 0;
for(int i=0,start=0,cnt=0;i<c.length;i++){
if(c[i]=='('){
cnt++;
}else {
cnt--;
if (cnt < 0) {
start = i + 1;
cnt = 0;
} else if (cnt == 0) {
res = Math.max(res, i - start + 1);
}
}
}
return res;
}
}Solution in Python Programming
class Solution(object):
def longestValidParentheses(self, s):
stack = [ -1 ] # boundary sign
max_deep = 0
for i, c in enumerate(s):
if (c == '('):
stack.append(i)
else:
if (stack[-1] != -1 and s[stack[-1]] == '('):
stack.pop()
max_deep = max(max_deep, i - stack[-1])
else: # invalid ')', push a new left boundary
stack.append(i)
return max_deepSolution in C# Programming
using System;
using System.Text.RegularExpressions;
public class Solution {
public int LongestValidParentheses(string s) {
Regex rgx = new Regex(@"\((-*)\)");
string result = rgx.Replace(s, @"-$1-"); while(!Object.ReferenceEquals(s, result)){ s = result; result = rgx.Replace(s, @"-$1-");
}
int max = 0;
foreach (Match match in Regex.Matches(s, @"-*"))
max = Math.Max(match.Value.Length, max);
return max;
}
}Also read,