Sponsored
Sponsored
This approach involves using a stack to keep track of indices of the opening parentheses. We iterate through the string and for each closing parenthesis, we pop from the stack to check if we have a matching opening parenthesis. By maintaining indices, we can calculate the length of valid substrings.
Time Complexity: O(n), where n is the length of the string. We traverse the string once.
Space Complexity: O(n), due to the stack that stores indices.
1import java.util.Stack;
2
3class Solution {
4 public int longestValidParentheses(String s) {
5 Stack<Integer> stack = new Stack<>();
6 stack.push(-1);
7 int maxLength = 0;
8
9 for (int i = 0; i < s.length(); i++) {
10 if (s.charAt(i) == '(') {
11 stack.push(i);
12 } else {
13 stack.pop();
14 if (stack.isEmpty()) {
15 stack.push(i);
16 } else {
17 maxLength = Math.max(maxLength, i - stack.peek());
18 }
19 }
20 }
21 return maxLength;
22 }
23
24 public static void main(String[] args) {
25 Solution solution = new Solution();
26 System.out.println(solution.longestValidParentheses(")()())"));
27 }
28}The Java solution uses a similar logic with a stack to maintain the opening parentheses' indices. It handles both opening and closing parentheses by adjusting the stack appropriately.
In this approach, we use a dynamic programming array where each entry at index i holds the length of the longest valid substring ending at that index. We iterate through the string, updating the DP array to keep track of valid pairs and their contributions to the overall length.
Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.
1
The C solution uses a DP array to accumulate the length of valid substrings. For each closing parenthesis, previous states are checked for forming valid pairs.