LeetCode 678: Valid Parenthesis String — Step-by-Step Visual Trace

Medium — String | Greedy | Stack

The Problem

Determine if a string containing parentheses ’(’, ’)’, and wildcards '' is valid, where '' can represent ’(’, ’)’, or an empty string.

Approach

Use a greedy approach by tracking the minimum and maximum possible count of open parentheses. For each character, update the bounds and check if a valid configuration exists.

Time: O(n) · Space: O(1)

Code

class Solution:
    def checkValidString(self, s: str) -> bool:
        lower = upper = 0

        for char in s:
            if char == "(":
                lower += 1
                upper += 1
            elif char == ")":
                lower = max(lower - 1, 0)
                upper -= 1
            else:  # char == '*'
                lower = max(lower - 1, 0)
                upper += 1

            if upper < 0:
                return False

        return lower == 0

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments