[BUG] - Possibly incorrect solutions in Editorial for 2116. Check if a Parentheses String Can Be Valid #26419
Description
LeetCode Username
davidmiheev
Problem Number, Title, and Link
https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/editorial/
Bug Category
Editorial
Bug Description
The second solution from editorial gives us open_brackets < 0 on some testcases. Is it ok? For example, on this testcase:
s = "())()))()(()(((())(()()))))((((()())(())"
locked = "1011101100010001001011000000110010100101"
open_brackets = -7
Language Used for Code
Python/Python3
Code used for Submit/Run operation
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
length = len(s)
# If length of string is odd, return false.
if length % 2 == 1:
return False
open_brackets = 0
unlocked_count = 0
# Iterate through the string to handle '(' and ')'.
for i in range(length):
if locked[i] == "0":
unlocked_count += 1
elif s[i] == "(":
open_brackets += 1
elif s[i] == ")":
if open_brackets > 0:
open_brackets -= 1
elif unlocked_count > 0:
unlocked_count -= 1
else:
return False
# Match remaining open brackets with unlocked characters.
balance_count = 0
for i in range(length - 1, -1, -1):
if locked[i] == "0":
balance_count -= 1
unlocked_count -= 1
elif s[i] == "(":
balance_count += 1
open_brackets -= 1
elif s[i] == ")":
balance_count -= 1
if balance_count > 0:
return False
if unlocked_count == 0 and open_brackets == 0:
break
if open_brackets > 0:
return False
print(open_brackets)
return TrueExpected behavior
I expected to see open_brackets (as a counter of open brackets) be always non-negative
Screenshots
Additional context
No response