LeetCode //C - 32. Longest Valid Parentheses

32. Longest Valid Parentheses

Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.
 

Example 1:

Example 2:

Example 3:

Constraints:

• 0 < = s . l e n g t h < = 3 ∗ 1 0 4 0 <= s.length <= 3 * 10^4 0<=s.length<=3∗104
• s[i] is ‘(’, or ‘)’.

From: LeetCode
Link: 32. Longest Valid Parentheses

---

Solution:

Ideas：

This function uses dynamic memory allocation for the stack to handle the worst-case scenario where all characters are ‘(’ and thus might be pushed onto the stack. It’s crucial to free the allocated memory to avoid memory leaks. The base variable acts as a marker for the start of a new potential valid substring. The length of the longest valid parentheses substring is updated whenever a valid pair is encountered, considering the current base or the last unmatched ‘(’ index stored in the stack.

Code:

int longestValidParentheses(char* s) {
    int maxLen = 0;
    int stackSize = 0;
    int* stack = (int*)malloc(sizeof(int) * (strlen(s) + 1)); // +1 for the base index
    int base = -1; // Base index before the first character

    for (int i = 0; s[i] != '\0'; ++i) {
        if (s[i] == '(') {
            stack[stackSize++] = i; // Push the index of '(' onto the stack
        } else { // When s[i] == ')'
            if (stackSize == 0) { // No matching '('
                base = i; // Update the base to the current index
            } else {
                --stackSize; // Pop the matching '(' index from the stack
                int validSubstringStart = (stackSize == 0) ? base : stack[stackSize - 1];
                maxLen = (maxLen > i - validSubstringStart) ? maxLen : i - validSubstringStart;
            }
        }
    }

    free(stack); // Clean up the allocated memory
    return maxLen;
}