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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestValidParentheses(string s) {
6 var stack = new Stack<int>();
7 stack.Push(-1);
8 int maxLen = 0;
9
10 for (int i = 0; i < s.Length; i++) {
11 if (s[i] == '(') {
12 stack.Push(i);
13 } else {
14 stack.Pop();
15 if (stack.Count == 0) {
16 stack.Push(i);
17 } else {
18 maxLen = Math.Max(maxLen, i - stack.Peek());
19 }
20 }
21 }
22 return maxLen;
23 }
24
25 static void Main(string[] args) {
26 Console.WriteLine(new Solution().LongestValidParentheses(")()())"));
27 }
28}The C# code applies the same stack-based logic, managing indices to calculate the longest valid parentheses.
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.