Longest valid Parenthesis || Newton School assignment solution || newton school contest Question ||

(contributed by Utkarsh Singh)

Longest valid Parenthesis  

Time Limit: 2 sec

Memory Limit: 128000 kB

Problem Statement

Given a string S consisting of opening and closing parenthesis '(' and ')'. Find length of the longest valid parenthesis substring.

Input

Each test case have one line string S of character '(' and ')' of length N.

Constraints:

1 <= N <= 105

Output

Print the length of the longest valid parenthesis substring.

Example

Input

((()

Output

2

Input

)()())

Output

4

                                           Solutions                                 

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

                      // Your code here

    Scanner sc = new Scanner(System.in);

    String str = sc.nextLine();

    Stack<Integer> Stack = new Stack<>();

    Stack.push(-1);

    int ans = 0;

   for(int i =0;i<str.length();i++)

       if(str.charAt(i)=='(') Stack.push(i);

       else{

           Stack.pop();

           if(Stack.isEmpty()) Stack.push(i);

           else ans = Math.max(ans,i-Stack.peek());

       }

       System.out.println(ans);

   

    }

}

                                              

if you don't know about next() and nextLine() read the table below :

 next()  

 

next()	nextLine()
It read input from the input device till we get the space character	It read input from the input device till we change the line
It is unable to read words with spaces in them.	It can read words with spaces in them.
After receiving a space, it stops reading the input.	Once you type "\n" or hit Enter, the input is finished being read.
After reading the input, it moves the pointer to the same line.	After reading the input, it moves the cursor to the following line.
Next(escape )'s sequence is space.	The nextLine() escaping sequence is "\n"
Syntax to scan input:  Scanner.next()	Syntax to scan input:  Scanner.next()

 

import java.io.*; // for handling input/output

import java.util.*; // contains Collections framework

// don't change the name of this class

// you can add inner classes if needed

class Main {

    public static void main (String[] args) {

                      // Your code here

    Scanner sc = new Scanner(System.in);

    String str = sc.nextLine();

    Stack<Integer> Stack = new Stack<>();

    Stack.push(-1);

    int ans = 0;

   for(int i =0;i<str.length();i++)

       if(str.charAt(i)=='(') Stack.push(i);

       else{

           Stack.pop();

           if(Stack.isEmpty()) Stack.push(i);

           else ans = Math.max(ans,i-Stack.peek());

       }

       System.out.println(ans);

   

    }

}