Codementor Events

Find the maximum pair of consecutive valid parenthesis

Published Jun 04, 2023

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;
    }
}

test case

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));
    }
}

build.gradle

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()
}
Discover and read more posts from we some
get started
post commentsBe the first to share your opinion
Show more replies