1
class Solution:
2
    def checkValidString(self, s: str) -> bool:
3
        left, right, star = (
4
            deque(),
5
            deque(),
6
            deque(),
7
        )  # indexes of all unmatched left right parens and all '*'
8
        # O(n) where n=len(s)
9
        for i, c in enumerate(s):
10
            if c == "(":  # we just append left paren's index
11
                left.append(i)
12
            elif c == ")":  # we check if we can find a match of left paren
13
                if left and left[-1] < i:
14
                    left.pop()
15
                else:
16
                    right.append(i)
17
            else:  #'*' case we just add the postion
18
                star.append(i)
19
        if not left and not right:
20
            return True
21
        elif not star:
22
            return False  # no star to save the string, return False
23
        l, r = 0, len(star) - 1
24
        # O(n) since star will be length less than n
25
        # Note: left, right,and star are always kept in ascending order! And for any i in left, j in right, i > j, or they would have been matched in the previous for loop.
26
        while l <= r:
27
            if left:
28
                if (
29
                    left[-1] < star[r]
30
                ):  # we keep using right most star to match with right most '('
31
                    left.pop()
32
                    r -= 1
33
                else:
34
                    return False  # even the right most '*' can not match a '(', we can not fix the string.
35
            if right:
36
                if right[0] > star[l]:
37
                    right.popleft()
38
                    l += 1
39
                else:
40
                    return False
41
            if not left and not right:
42
                return True  # if after some fix, all matched, we return True