Consecutive valid parenthesis is when both opening and closing brackets are present just after another and in a consecutive manner. For example {}[]()
all are valid and consecutive, hence Consecutive valid parenthesis is 3.
package org.wesome.dsalgo;
import java.util.Stack;
public class ConsecutiveValidParenthesis {
public static int consecutiveValidParentheses(String s) {
int maxlen = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
// when encounter '(' push the index onto stack
if (s.charAt(i) == '(') {
stack.push(i);
} else {
// when encounter ')', pop the topmost element first
// then subtract the index from the peek element (if the stack is not empty)
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
// keep the longest length of the valid substrings
maxlen = Math.max(maxlen, i - stack.peek());
}
}
}
return maxlen;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
public class ConsecutiveValidParenthesisTest {
@Test
void consecutiveValidParenthesesTest1() {
String parenthesis = ")()())";
Assertions.assertEquals(4, ConsecutiveValidParenthesis.consecutiveValidParentheses(parenthesis));
}
@Test
void consecutiveValidParenthesesTest2() {
String parenthesis = ")()())()";
Assertions.assertEquals(4, ConsecutiveValidParenthesis.consecutiveValidParentheses(parenthesis));
}
@Test
void consecutiveValidParenthesesTest3() {
String parenthesis = ")(()())()";
Assertions.assertEquals(8, ConsecutiveValidParenthesis.consecutiveValidParentheses(parenthesis));
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}