Description:
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Examples:
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: 0Solution in Python:
This approach uses a stack to keep track of the indices of the characters in the string. The main idea is to use the stack to remember the positions of unmatched '(' and to calculate the lengths of valid parentheses substrings as we process the string.
Python
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] # Initialize stack with -1 to handle edge case
max_len = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_len
# Example usage:
solution = Solution()
print(solution.longestValidParentheses("(()")) # Output: 2
print(solution.longestValidParentheses(")()())")) # Output: 4
print(solution.longestValidParentheses("")) # Output: 0Step-by-step explanation:
- Initialize the Stack:
- We start by initializing the stack with
-1. This helps handle edge cases where the valid substring starts at the beginning of the string. - We also initialize a variable
max_lento keep track of the maximum length of valid parentheses found.
- We start by initializing the stack with
- Iterate Through the String:
- We iterate through the string, checking each character.
- If the character is
'(', we push its index onto the stack. - If the character is
')', we pop the top of the stack. This popping helps match the current')'with the last unmatched'('. - After popping, if the stack is empty, it means there are no unmatched
'('left to match with the current')', so we push the current index onto the stack. This helps in resetting the starting point for the next potential valid substring. - If the stack is not empty after popping, we calculate the length of the current valid substring by subtracting the index of the top element of the stack from the current index. We update
max_lenwith this length if it is greater than the currentmax_len.
- Return the Maximum Length:
- After processing the entire string,
max_lencontains the length of the longest valid parentheses substring.
- After processing the entire string,
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
// Initialize the stack with -1 to handle the base case
let stack = [-1];
// Variable to keep track of the maximum length of valid parentheses
let max_len = 0;
// Iterate through the string
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
// Push the index of '(' onto the stack
stack.push(i);
} else {
// Pop the top of the stack
stack.pop();
if (stack.length === 0) {
// If the stack is empty, push the current index onto the stack
stack.push(i);
} else {
// Calculate the length of the current valid substring
max_len = Math.max(max_len, i - stack[stack.length - 1]);
}
}
}
return max_len;
};
// Example usage:
console.log(longestValidParentheses("(()")); // Output: 2
console.log(longestValidParentheses(")()())")); // Output: 4
console.log(longestValidParentheses("")); // Output: 0Solution in Java:
Java
class Solution {
public int longestValidParentheses(String s) {
// Initialize the stack with -1 to handle the base case
Stack<Integer> stack = new Stack<>();
stack.push(-1);
// Variable to keep track of the maximum length of valid parentheses
int maxLen = 0;
// Iterate through the string
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// Push the index of '(' onto the stack
stack.push(i);
} else {
// Pop the top of the stack
stack.pop();
if (stack.isEmpty()) {
// If the stack is empty, push the current index onto the stack
stack.push(i);
} else {
// Calculate the length of the current valid substring
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.longestValidParentheses("(()")); // Output: 2
System.out.println(solution.longestValidParentheses(")()())")); // Output: 4
System.out.println(solution.longestValidParentheses("")); // Output: 0
}
}Solution in C#:
C#
public class Solution {
public int LongestValidParentheses(string s) {
// Initialize the stack with -1 to handle the base case
Stack<int> stack = new Stack<int>();
stack.Push(-1);
// Variable to keep track of the maximum length of valid parentheses
int maxLen = 0;
// Iterate through the string
for (int i = 0; i < s.Length; i++) {
if (s[i] == '(') {
// Push the index of '(' onto the stack
stack.Push(i);
} else {
// Pop the top of the stack
stack.Pop();
if (stack.Count == 0) {
// If the stack is empty, push the current index onto the stack
stack.Push(i);
} else {
// Calculate the length of the current valid substring
maxLen = Math.Max(maxLen, i - stack.Peek());
}
}
}
return maxLen;
}
}