“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

How to find the longest valid (well-formed and continuous) parenthesis substring

Implementation approach

Finding the length of the longest valid parenthesis string is more complicated than verifying that the entire string is valid.

Verify that the entire string is valid, as long as one does not conform to the rule, can be determined.

Finding the length of the longest valid parenthesis string requires traversing the entire string.

Valid parenthesis string exists in the middle of substrings that do not conform to the rule. We need to count the length of each substring that conforms to the rule and then compare the size to find the length of the longest valid parenthesis string. Of course, you can also determine the maximum substring length in continuous traversal. Also determine and exclude substrings that do not conform to the rule.

So how do you determine the valid parenthesis substring length in a given string?

As we traverse the string, the table below is incremented for each character. We maintain the subscript of each character through the stack, and determine the length of the substring by determining the beginning and end subscripts of a regular parenthesis string.

Particular way is we used an array for a stack structure, and put a value of 1 in the first array, represents a placeholder, because when a subrange conform to the rules of the brackets are into the stack and the stack, the array is empty, we cannot judge the substring first start character position in the table below, thus unable to get the whole length of the substring. When a close parenthesis is encountered and the array is empty, we need to put the table below the close parenthesis into the array, representing the starting position of the next conforming substring.

The code on

Line 227-230 returns 0 if the given string length is less than 1.

Line 232 defines an array to represent the stack structure and places an initial element, -1, that represents the preceding subscript of a regular parenthesized substring.

Line 233 defines the valid parenthesis length.

Line 235-236 puts the following table in the current position into the array to determine that the character is in the left parenthesis, traversing the string with the first character starting with a subscript of 0.

On line 238, when the character is in the closing bracket, we first remove the last element in the array.

On lines 239-240, when the array is empty, we put the subscript of the current closing bracket into the array to represent the starting position of the next conforming substring.

$manLength = $manLength; $manLength = $manLength; $manLength = $manLength; $manLength = $manLength;

The maximum valid parenthesis length can be obtained by traversing the entire string.