678. Valid Parenthesis String

📝 Problem Details

• Title: 678
• Link: https://leetcode.com/problems/valid-parenthesis-string/
• Difficulty: Medium
• Tags/Categories: Greedy

input string s can only contain characters ( ) and * return true if s is valid 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 one * could be treated as a single right or left parenthesis or an empty string ""

💭What Were My Initial Thoughts?

brute force: three pass simulation (backtracking)
- check if s is valid assuming * are empty
- check if s is valid assuming * are (
- check if s is valid assuming * are )

can possibly employ a greedy approach that condenses the same core idea into a single pass through

💡 Explanation of Solution

Greedy Approach: track possible valid parentheses by maintaining:
- low : minimum number of open brackets possible
- high : the maximum number of open brackets possible

traverse the string once from left to right
adjust low and high based on:
( → Increase low AND high (must add an open bracket).
) → Decrease low AND high (must close an open bracket).
* → Incrase high (use as `(` ) but decrease low (use as `)` or "")

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0; 
 
        for (char c : s) {
            if (c == '(') {
                low++;
                high++;
            } 
            else if (c == ')') {
                low = max(0, low - 1);
                high--;
            } 
            else { // '*'
                low = max(0, low - 1); // '*' acts as ')'
                high++;                // '*' acts as '('
            }
 
            if (high < 0) return false; // Too many closing brackets
        }
 
        return low == 0; // Only valid if all open brackets are balanced
    }
};