Valid Parenthesis String Leetcode Problem 678 [Python Solution]

The problem at hand is to determine whether a given string, s, containing only three types of characters – ‘(‘, ‘)’, and ‘*’, is a valid parenthesis string.

The rules defining a valid string are as follows:

1. Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
2. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
3. Left parenthesis ‘(‘ must precede the corresponding right parenthesis ‘)’.
4. ‘*’ could be treated as a single right parenthesis ‘)’, a single left parenthesis ‘(‘, or an empty string “”.

Constraints

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

Example 1:

• Input: s = “()”
• Output: true

Example 2:

• Input: s = “(*)”
• Output: true

Example 3:

• Input: s = “(*))”
• Output: true

Efficient Python Code Solution

We will explore an efficient Python code solution for this problem.

It’s a greedy approach, and it offers a time complexity of O(n).

def checkValidString(s: str) -> bool:
    leftMin, leftMax = 0, 0

    for c in s:
        if c == "(":
            leftMin, leftMax = leftMin + 1, leftMax + 1
        elif c == ")":
            leftMin, leftMax = leftMin - 1, leftMax - 1
        else:
            leftMin, leftMax = leftMin - 1, leftMax + 1
        if leftMax < 0:
            return False
        if leftMin < 0:  # required because -> s = ( * ) (
            leftMin = 0
    return leftMin == 0

In this code, we maintain two variables, leftMin and leftMax, representing the range of possibilities for the number of open left parentheses.

We iterate through the string, adjusting these variables based on the characters encountered.

If leftMax ever becomes negative, the string cannot be valid.

Additionally, we ensure that leftMin never becomes negative, resetting it to zero if needed.

Time and Space Complexity

• Time Complexity: O(n) – The algorithm scans through the string once.
• Space Complexity: O(1) – It uses only a constant amount of additional space.

Related Interview Questions By Company:

• Find The Kth Largest Integer In The Array LeetCode
• Merge Intervals LeetCode
• Insert Delete Get Random O(1) LeetCode

Related Interview Questions By Difficulty:

• Longest Turbulent Array LeetCode
• Two City Scheduling LeetCode
• Partition Labels LeetCode

Conclusion

Solving the Valid Parenthesis String problem can be challenging, but with the efficient Python code solution, we can determine the validity of a string in a time-efficient manner.

This solution optimally handles the various possibilities presented by wildcard characters and adheres to the rules of a valid string.

Feel free to experiment with the provided code and explore more about this problem on LeetCode.

If you found this guide helpful, please consider liking, subscribing, and supporting the our platform.

If you have any questions, suggestions, or comments, please share them below.

Happy coding!