0678 - Valid Parenthesis String (Medium)

Problem Link

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

Problem Statement

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'.

Approach 1: Greedy

If there were no $'*'$ characters, we could easily do this, using an integer, and just tracking $'('$ chars as a $+1$ and $')'$ as a $-1$. Returning False, if the result ever goes negative, and True if the final result is $0$.

The $'*'$ throws a little wrench, so instead we can track two integers. Both a min balance and a max balance. That is for the min balance we can do the same thing and treat all $'*'$ characters as $')'$ but reset to zero if the result ever goes negative. This would be us converting a $'*'$ to something else.

Then for the max balance, we can do the same, but treat all $'*'$ as $'('$. Then we know if the max balance ever reaches negative, that we absolutely can't create a valid string, as we don't have enough $'*'$, and as long as our max balance is positive, we can reset our min balance to 0 to convert our $'*'$ into something else.

If in the end, our min balance is 0, then we can create a balanced string.

Time Complexity: $O(n)$, we just need to iterate through each character once.

Space Complexity: $O(1)$, we can do this in constant time just tracking our max and min balances.

Python

Written by @ColeB2

class Solution:
    # track 2 values, min_balance and max_balance which represent
    # the balance of parenthesis. Positive means, we have more '('
    # negative means we have more ')'.
    # The min_balance value will represent the lowest balance of
    # parenthesis. This means we always convert a '*' to a ')',
    # without going negative. This means we can reconvert a '*' 
    # if the value ever does go negative.
    # The max_balance value will represent the highest balance of
    # parenthesis. Meaning we will always convert a '*' into a '('
    # If the max_balance ever hits negative, it means we have way
    # too many ')' to create a balanced parenthesis string.
    # So as long as max_balance is positive, we can always reset
    # min_balance to 0, as we can convert a '*' into something else.
    def checkValidString(self, s: str) -> bool:
        # initialize min and max balances
        min_balance, max_balance = 0, 0
        # iterate through each character in the string
        for ch in s:
            if ch == '(':
                # Open parenthesis always adjust our balance positive
                min_balance += 1
                max_balance += 1
            elif ch == ')':
                # close parenthesis lowers both balances, but if
                # If the min reaches negative, reset it to 0.
                min_balance = max(0, min_balance - 1)
                max_balance -= 1
            elif ch == '*':
                # For min balance consider the '*' a ')', if we
                # reach negative, convert it to something else.
                min_balance = max(0, min_balance - 1)
                # add it as open '(' parenthesis.
                max_balance += 1
            # max ever reaches 0, since we are always converting '*'
            # into '(', it means we have way too many ')'.
            if max_balance < 0:
                return False
        # if our min_balance reached 0, it means we have an even number
        # of parenthesis, so then it returns True. If not, then it will
        # return False.
        return min_balance == 0