LeetCode Entry

678. Valid Parenthesis String

04.10.2026 medium 2026 kotlin rust

Balance braces with wildcard

678. Valid Parenthesis String medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1502

Problem TLDR

Balance braces with wildcard

Intuition

• Dp solution: dfs and make a choice at a wildcards
• Forward-backward pass: treat wildcard as open brace, should check both ways
• Balance range solution: open brace do +1 to range, close do -1, wildcard widens the range

Approach

• lower should be clamped to zero, upper should not go less than zero

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun checkValidString(s: String): Boolean {
        var l = 0; var h = 0
        for (c in s) {
            l = maxOf(0, l + if (c == '(') 1 else -1)
            if ((if (c == ')') --h else ++h) < 0) return false
        }
        return l == 0
    }

    pub fn check_valid_string(s: String) -> bool {
        let (mut l, mut h) = (0, 0);
        s.bytes().all(|b| {
            l = (l + if b == b'(' { 1 } else { -1 }).max(0);
            h += if b == b')' { -1 } else { 1 }; h >= 0
        }) && l == 0
    }