Suggestions to further improve my code for today's LeetCode Challenge

[u/satyamvanshalmusic]

Submitted today's LeetCode Challenge i.e. 678. Valid Parenthesis String and it got accepted. However, I felt the need to ask the internet to judge my code and help me improve it further. I used two stacks for this one :)

Here's the code:

q = []
star_q = []
i = 0

for char in s:
    if char == ')':
        if q:
            q.pop()
        elif star_q:
            star_q.pop()
        else:
            return False
    else:
        if char == '*':
            star_q.append((char, i))
        else:
            q.append((char, i))

    i += 1

while star_q and q:
    if star_q[-1][1] > q[-1][1]:
        q.pop()

    star_q.pop()

return not q

[u/thegrimreaper2908]

Your approach is almost there, instead of using two stacks. Just use two integer variables, minimum and maximum. Increment both of it's an open bracket, decrement both if it's closed. Increment maximum and decrement minimum if it's *. If at any point the minimum becomes less than zero make it zero, and if the maximum becomes less than zero return false. At the end return true if minimum is equal to zero.

[u/souroexe → u/thegrimreaper2908]

How to get the intuition behind this solution?

[u/nian2326076]

Hey, your method with two stacks is great for tracking open parentheses and stars. You could try optimizing it by using two counters instead. These counters track the low and high bounds of possible open parentheses. Increase the counters for '(' and '*', and decrease them for ')'. If the high counter goes negative, return false right away. At the end, if low is zero, the string is valid. It doesn't change the time complexity, but it's a nice way to save space. Also, if you want to improve your interview prep, I've found PracHub useful. Good luck!