Problem statement

https://leetcode.com/problems/valid-parenthesis-string/

Solution

Let us on each step calculate the balance between open and closed brackets. At any moment of time we will have interval [beg, end] of possible balances. We start with [0, 0] interval, for empty string it is balanced. Then if we have open bracket, we increase these two values, if we have closed bracket, we decrease them. Also at any moment of time we can not have negative balance: it means that this substring is not valid, so we use max(0, beg - 1). In the end we check if beg = 0.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def checkValidString(self, s):
        beg, end = 0, 0
        for el in s:
            if el == "(":
                beg, end = beg + 1, end + 1
            elif el == ")":
                if end == 0:
                    return False
                else:
                    beg, end = max(0, beg - 1), end - 1
            else:    #elem == "*"
                beg, end = max(0, beg - 1), end + 1
        return beg == 0

Remark

There is also O(n^3) dp solution, where dp[i][j] is true if s[i:j+1] can be built as valid string.