Longest Valid Parentheses
Longest Valid Parentheses (100 Marks)
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Input Format
Input 1: "(()"
Input 2: ")()())"
Constraints
NAOutput Format
For Input 1, The longest valid parentheses sub-string is "()"
For Input 2, The longest valid parentheses sub-string is "()()"
Sample TestCase 1 :
Input "()(()))))"
Output 6
SOLUTION Java8
/*
* Enter your code here. Read input from STDIN. Print your output to STDOUT.
* Your class should be named CandidateCode.
*/
import java.io.*;
import java.util.*;
public class CandidateCode {
public static void main(String args[] ) throws Exception {
//Write code here
Scanner scan = new Scanner ( System.in );
String s = scan.nextLine();
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
System.out.print(maxans);
//Code ends here
}
}
OUTPUT:
Algorithm:
Using Stack
Source: https://leetcode.com/problems/longest-valid-parentheses/solution/
Instead of finding every possible string and checking its validity, we can make use of stack while scanning the given string to check if the string scanned so far is valid, and also the length of the longest valid string. In order to do so, we start by pushing onto the stack.For every encountered, we push its index onto the stack.
For every encountered, we pop the topmost element and subtract the current element's index from the top element of the stack, which gives the length of the currently encountered valid string of parentheses. If while popping the element, the stack becomes empty, we push the current element's index onto the stack. In this way, we keep on calculating the lengths of the valid sub strings, and return the length of the longest valid string at the end.
See this example for better understanding.
Comments
Post a Comment