leetcode/32_longest_valid_parentheses

32_longest_valid_parentheses

dz / leetcode / 32_longest_valid_parentheses

Summary

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

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/longest-valid-parentheses

intuition
content I've done substring problems in the past, so I'm trying to remember what was involved with those. I've also dealt with parentheses validation problems, so there may be some intuition there.
children backtrack_approach, even_number, starts_with_left, valid_inside_invalid

starts_with_left
content Every valid parantheses substring will start with one left paren, and therefore must have a corresponding right paren.
parents intuition

even_number
content there will always been an even number of parens, with an equal number of left/right parens.
parents intuition

valid_inside_invalid
content valid substrings can be encapsulated inside of larger invalid strings. how to tackle those?
parents intuition

backtrack_approach
content Keep track of left parens, and backtrack when right parens are found.
children somehow_drop_segments_and_keep_track_of_longest_valid
parents intuition

somehow_drop_segments_and_keep_track_of_longest_valid
content somehow, there needs to be a way to keep track of longest substrings during backtracking.
children find_previous_valid_right
parents backtrack_approach

find_previous_valid_right
content when invalid rigth is found, somehow find last right value. this will have a corresponding left value.
parents somehow_drop_segments_and_keep_track_of_longest_valid

editorial
content editorial
children approach_1_bruteforce

approach_1_bruteforce
content brute force: consider every possible non-empty substring from the given string and check whether it's a valid parentheses or not. Use the stack's method.
children vs_approach_3
parents approach_3_stack, editorial

vs_approach_3
content approach 1 works by brute forcing every possible combination and using the stack method to check if each substring is valid.
parents approach_1_bruteforce

approach_2_dynamic
content dynamic programming

approach_3_stack
content Instead of checking every possible string to see if it's valid, use a stack while scanning to see if given string scanned so far is valid, and to find the length of the longest string.
children init_push_neg_1, approach_1_bruteforce (similar)

init_push_neg_1
content to begin, push negative 1 onto stack
children every_left_push_index
parents approach_3_stack

every_left_push_index
content for every left, push the index onto the stack
children every_right_pop_topmost
parents init_push_neg_1

every_right_pop_topmost
content every right encounter, pop topmost element from stack
parents every_left_push_index

empty_stack_push_elem_cur_index
content If, while popping the element, stack is empty, push the current index onto stack, can continue calculating length of valid substrings

approach_4_without_extra_space
content two counters, left and right. traverse string left towards right. for every lpar, increment left, for every rpar, incremnt right. when left=right, calc length of current valid string and keep track of max leng. if right greater than left, reset left/right to 0. traverse from right to left using similar procedure