C Exercises: Length, longest valid parentheses substring

Last update on March 21 2025 12:37:15 (UTC/GMT +8 hours)

16. Longest Valid Parentheses Substring Variants

Write a C program to find the length of the longest valid (correct-formed) parentheses substring of a given string.

C Code:

#include <stdio.h>
#include <stdlib.h>

static int longest_valid_parentheses(char* parentheses_str)
{
    int cap = 8000, error = -1;
    int length = 0, max_length = 0;
    char *p = parentheses_str;
    int *pstack = malloc(cap * sizeof(int));
    int *top = pstack;

    while (*p != '\0') {
        if (*p == '(') {
            if (top + 1 - pstack >= cap) {
                cap *= 2;
                pstack = realloc(pstack, cap * sizeof(int));
            }
            *top++ = p - parentheses_str;
        } else {
            if (top > pstack) {
                if (--top == pstack) {
                     length = p - (parentheses_str + error);
                } else {
                    length = p - (parentheses_str + *(top - 1));
                }
                if (length > max_length) {
                    max_length = length;
                }
            } else {
                error = p - parentheses_str;
            }
        }
        p++;
    }
    return max_length;
}

int main(void)
 {
    char main_str[] = "(()))";
	printf("\nOriginal Parentheses string: %s", main_str);
	printf("\nLength of longest parentheses: %d", longest_valid_parentheses(main_str));
    return 0;
 }

Sample Output:

Original Parentheses string: (()))
Length of longest parentheses: 4

Pictorial Presentation:

C Programming: Find the length of the longest valid parentheses substring of a given string.

Flowchart:

For more Practice: Solve these Related Problems:

Write a C program to find the length of the longest valid parentheses substring using a stack-based method.
Write a C program to compute the longest valid parentheses substring using dynamic programming.
Write a C program to return both the length and starting index of the longest valid parentheses substring.
Write a C program to extract and display the longest valid parentheses substring from the input string.

C Programming Code Editor:

Contribute your code and comments through Disqus.

Previous C Programming Exercise: Divide two integers without multiply, divide, modulating.
Next C Programming Exercise: Sum of all the multiples of 3 or 7 below 100.