Longest Valid Parentheses - CPP Solution

1. Introduction

In this post, we'll be diving into a challenging and interesting problem often encountered in programming interviews - finding the length of the longest valid (well-formed) parentheses substring. This problem requires a good grasp of string processing and the use of data structures like stacks in C++.

Problem

The task is to write a function in C++ that, given a string containing just the characters '(' and ')', returns the length of the longest valid (well-formed) parentheses substring.

2. Solution Steps

1. Use a stack to keep track of indices of the parentheses.

2. Iterate through the string, processing each character.

3. If a character is '(', push its index onto the stack.

4. If it's ')', pop the top element from the stack.

5. If the stack becomes empty, push the current index onto the stack.

6. Otherwise, calculate the length of the current valid substring and update the maximum length found so far.

7. Continue this process for each character in the string.

3. Code Program

#include <iostream>
#include <stack>
using namespace std;

// Function to find the length of the longest valid parentheses substring
int longestValidParentheses(string s) {
    int maxLength = 0;
    stack<int> indices;
    indices.push(-1); // Base for indices difference calculation

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            // Push the index of '(' onto the stack
            indices.push(i);
        } else {
            // Pop the top element for the matching '('
            indices.pop();
            if (indices.empty()) {
                // Push current index as a new base if the stack is empty
                indices.push(i);
            } else {
                // Calculate the length of the current valid substring
                maxLength = max(maxLength, i - indices.top());
            }
        }
    }
    return maxLength;
}

int main() {
    string input = "(()";
    cout << "Longest valid parentheses length: " << longestValidParentheses(input) << endl;
    return 0;
}

Output:

Longest valid parentheses length: 2

Explanation:

1. The input string "(()" is processed character by character.

2. Each '(' character's index is pushed onto the stack.

3. For each ')', the stack is popped, and the length of the valid substring is calculated.

4. The longest valid substring in this case is "()", with a length of 2.

5. The function correctly calculates the length by using a stack to track the positions of parentheses and ensuring that the substring is well-formed.