32_longest_valid_parentheses
dz / leetcode / 32_longest_valid_parenthesesSummary
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Node Tree
- approach_2_dynamic
- approach_3_stack
- approach_4_without_extra_space
- editorial
- empty_stack_push_elem_cur_index
- intuition
- URL
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 |