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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5int longestValidParentheses(const char *s) {
6 int max_len = 0, n = strlen(s);
7 int *stack = (int *)malloc((n + 1) * sizeof(int));
8 int top = -1;
9 stack[++top] = -1;
10 for (int i = 0; i < n; i++) {
11 if (s[i] == '(') {
12 stack[++top] = i;
13 } else {
14 if (top > -1) top--;
15 if (top == -1) {
16 stack[++top] = i;
17 } else {
18 int len = i - stack[top];
19 if (len > max_len) max_len = len;
20 }
21 }
22 }
23 free(stack);
24 return max_len;
25}
26
27int main() {
28 char s[] = "()((()))";
29 printf("%d", longestValidParentheses(s));
30 return 0;
31}In this C implementation, the solution uses a stack to track indices of opening parentheses. A sentinel -1 is pushed initially to handle edge cases, such as the first valid substring extending to the start.
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.