Check if a Parentheses String Can Be Valid - Leetcode 2116 - Python

Показать описание

0:00 - Read the problem
0:30 - Drawing Explanation
13:27 - Coding Explanation
16:52 - Coding Explanation 2

leetcode 2116

#neetcode #leetcode #python

NeetCodeIO

Рекомендации по теме

Комментарии

"It is one of those algorithms, where the less you think about it, you might think 'Okay I fully understand it and it definitely makes a lot of sense why that solution works' but the more you think about it, the less sure you become that solution would actually work" I think this was spot on after reading the space optimized solution. 😓💯💯 Thanks for the explaination, it was great as usual. 💯

arjunprasad

Pretty brutal for a Medium, but definitely doable after reading the hints.

moralized

Great explanation! 🚀 Another small optimization to the constant space approach (early return condition) similar to the one mentioned at 19:50
# there must be at least as many unlocked parentheses leftover as the remaining locked parentheses
if unlocked_cnt < locked_cnt:
return False

cs-xigc

Correct me if I am wrong somewhere :

1. The unlocked stack is to keep track of wildcard indices ie positions which are modifiable.

2. First, we tried to balance any closing bracket ')' by matching it with any previous opening bracket '(' or matching it with a wildcard/unlocked position. If we are unable to do so for any closing bracket, we return false.

3. Once we have done that, if we find that the opening brackets stack is not empty, it means we have a surplus of opening brackets which need a matching closing bracket. We have already matched closing brackets. So we will have to use wildcard/unlocked indices.
We need to match it with remaining wildcard/unlocked positions. If we are unable to do so, then we return false.

4. So, now we have matched all the opening and closing brackets, so the string should be balanced.

5. If the unlocked stack is still not empty, it does not have any affect since, the string is already balanced. These positions represent unused modifiable characters that could have been used for balancing but were not needed because the sequence was already balanced. The key condition is whether open brackets stack is empty, which determines if the string is balanced.

arjunprasad

My goal is to outwork you with the daily leetcode questions, do all of them, and on a day that you dont do a video on the daily, I do that on my own.

justelis

19:15 I did the same 2 pass code😃 My thought process aligns with NeetCode day by day after watching him 😎❤️

pRot

This may not be the most optimal solution out there, but you can think of the unlocked positions as blanks, since you can do whatever you want with them, then it becomes exactly same to leetcode 678 question of Valid Parantheses String, which is much easier to implement

rhitambhuiya

After going through a lot of solution descriptions & videos. It is very clear on what the solution needs to be but very little explanation on why the solution works. In other words the question that was unanswered for me is "How does balancing the count of locked close & open brackets ensure that the original input is a valid parentheses string?"
If you have the same question as me hopefully the following approach will make things clear.

Consider the following input
-)(--)---)----(()(----

To begin with, let us ignore all the unlocked characters
)())(()(

Now try balancing them on its own and get the unbalanced ones
))((
The indices (0-based) that correspond to unbalanced ones are 1, 9, 14, 17.

The solutions at this point state that if you can find unlocked characters on left of unbalanced closed brackets & right of unbalanced open brackets, then the input string itself is valid.

Let us assign open bracket to indices 0 & 7 and close bracket to indices 19 & 21.
This converts the input string to
()(--)-(-)----(()(-)-)
and input string without unassigned characters to ()()()(()()) which is a valid string.

At this point we have 10 unassigned characters. The important observation here is that you can introduce 2 unassigned characters at any location of a valid string and you can ensure that string stays valid.
I will try doing this to above string with 2 unassigned characters each from left
()(--)-(-)----(()(-)-) CURRENT 10
()(())-(-)----(()(-)-) 8
()(())(())----(()(-)-) 6
()(())(())()--(()(-)-) 4
()(())(())()()(()(-)-) 2
()(())(())()()(()())() 0

TLDR: The important observation here is that you can introduce 2 unassigned characters at any location of a valid string and you can ensure that string stays valid.

Karthikheb

Reading left to right you can just count the number of locked '( ' then replace unlocked with '( ' until you have n // 2 ' ( ' total and it work

ndd

I was trying to solve it using stack for almost 2 hours, Then I though it's impossible but after just watching your video you said 2 stack and that's it, it took me 2mins after that. But the question is how do we come up with this solution. it's Navdeep.

avishjain

What if the question was to return a valid string if it exists? in that case, is backtracking the only solution or is there something better than that?

jimizuka-bkct

what is the name for last solution? I've seen it for multiple problems now I got to know??? is it algorithm or just intuition based coding when we traverse forward then backward?

amanshad

For the example at 5:40, shouldn't this still work fine? We just need to see if it is possible, not what combination of parentheses are needed to make it valid. Also, unless there wasn't a test case for this, this method worked fine for me when I did it.

salami

i think the second solution intuition is that there is no "two fixed parentheses using the same wildcard" because well first they have to be different directions, and at that point they would cancel each other out, as a matter of fact the worst case scenario would be when none match each other which this algorithm accounts for, correct if am wrong plz 👍

pastori

9:35 Why does the example (x)x)xx) pass? There is an x between positions 0 and 2. No matter the state of x, it still won’t close correctly.

JamesBond-mqpd

"We're going to need you to come up with this 'non-sensical' algorithm in 15 minutes, mmmmkay" - Interviewers probably (ref: &t=483s)

sntnmjones

The handling of the open parenthesis was a pain in the ass

travian

If neetcode said this problem is hard then this problem is really hard

vishaalkumaranandan

no wayyy! 4:05 thats how i approached it, neetcode the

MohanRam-mqpk

678. Valid Parenthesis String, this question also can be solve with same algo as 2116. only change is we not need to check unlocked stack..

siddhesh

Check if a Parentheses String Can Be Valid - Leetcode 2116 - Python

Check if a Parentheses String Can Be Valid - Leetcode 2116 - Python

Check if a Parentheses String Can Be Valid | Leetcode 2116

Valid Parenthesis String - Leetcode 678 - Python

Leetcode 2116 Check if a Parentheses String Can Be Valid - Interesting Problem, Interesting Solution

Valid Parentheses - Stack - Leetcode 20 - Python

2116. Check if a Parentheses String Can Be Valid - Day 12/31 Leetcode January Challenge

2116. Check if a Parentheses String Can Be Valid | Stack | Constant Space

LeetCode 2116: Validate Parentheses Strings Efficiently! 🧐✅ | Step-by-Step Guide

Check if a Parentheses String Can Be Valid | Detailed Intuition | 2 Approaches | Leetcode 2116 | MIK

Check if There Is a Valid Parentheses String Path | Leetcode 2267 | Simple DFS | Live coding session

#2116 Check if a Parentheses String Can Be Valid

2267. Check if There Is a Valid Parentheses String Path (Leetcode Hard)

Check if a Parentheses String Can Be Valid - LeetCode

Leetcode 2267. Check if There Is Valid Parentheses String Path

2116. Check if a Parentheses String Can Be Valid (Leetcode Medium)

Check if a Parentheses String Can Be Valid | Leetcode - 2116

Leetcode Valid Parentheses ANIMATED EXPLANATION

HOW TO NAIL LeetCode Interview Questions - Valid Parentheses (EASY)

Generate Parentheses - Stack - Leetcode 22

Leetcode 2116. Check if a Parentheses String Can Be Valid

LeetCode 2116 - Check if a Parentheses String Can Be Valid :: Resolução de Problemas de Programação...

valid parenthesis string leetcode | valid parentheses string leetcode python | leetcode

2116. Check if a Parentheses String Can Be Valid in java | Easy Solution | Leetcode

Check if a Parentheses String Can Be Valid | Leetcode