Valid Parenthesis String - LeetCode Daily Challenge

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

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public boolean checkValidString(String s) {
        int openCount = 0;
        int closeCount = 0;
        int length = s.length() - 1;
        
        for (int i = 0; i <= length; i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '*') {
                openCount++;
            } else {
                openCount--;
            }
            if (s.charAt(length - i) == ')' || s.charAt(length - i) == '*') {
                closeCount++;
            } else {
                closeCount--;
            }
            
            if (openCount < 0 || closeCount < 0) {
                return false;
            }
        }
        
        return true;
    }
}

C++ Code

class Solution {
public:
    string checkValidString(string s) {
        int openCount = 0;
        int closeCount = 0;
        int length = s.length() - 1;
        
        for (int i = 0; i <= length; i++) {
            if (s[i] == '(' || s[i] == '*') {
                openCount++;
            } else {
                openCount--;
            }
            if (s[length - i] == ')' || s[length - i] == '*') {
                closeCount++;
            } else {
                closeCount--;
            }
            
            if (openCount < 0 || closeCount < 0) {
                return false;
            }
        }
        
        return true;
    }
};

Python Code

class Solution:
    def checkValidString(self, s: str) -> bool:
        open_count = 0
        close_count = 0
        length = len(s) - 1
        
        for i in range(length + 1):
            if s[i] == '(' or s[i] == '*':
                open_count += 1
            else:
                open_count -= 1
            if s[length - i] == ')' or s[length - i] == '*':
                close_count += 1
            else:
                close_count -= 1
            
            if open_count < 0 or close_count < 0:
                return False
        
        return True

Javascript Code

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    let openCount = 0;
    let closeCount = 0;
    const length = s.length - 1;
    
    for (let i = 0; i <= length; i++) {
        if (s[i] === '(' || s[i] === '*') {
            openCount++;
        } else {
            openCount--;
        }
        if (s[length - i] === ')' || s[length - i] === '*') {
            closeCount++;
        } else {
            closeCount--;
        }
        
        if (openCount < 0 || closeCount < 0) {
            return false;
        }
    }
    
    return true;
};

Go Code

func checkValidString(str string) bool {
    openCount := 0
    closeCount := 0
    length := len(str) - 1

    for i := 0; i <= length; i++ {
        if str[i] == '(' || str[i] == '*' {
            openCount++
        } else {
            openCount--
        }
        if str[length-i] == ')' || str[length-i] == '*' {
            closeCount++
        } else {
            closeCount--
        }

        if openCount < 0 || closeCount < 0 {
            return false
        }
    }

    return true
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(1)