object ValidParenthesisString { def main(args: Array[String]): Unit = { val input = "(*))" val isValid = checkValidString(input) if (isValid) println(s"$input is a valid parenthesis string.") else println(s"$input is not a valid parenthesis string.") } def checkValidString(s: String): Boolean = { var low = 0 // Minimum possible open parentheses count. var high = 0 // Maximum possible open parentheses count. for (char <- s) { // Lower bound can be decreased by '*', but not below 0. if (char == '(') { low += 1 high += 1 } else if (char == ')') { low = Math.max(low - 1, 0) high -= 1 } else { // Asterisk '*' low = Math.max(low - 1, 0) // Treat '*' as '('. high += 1 // Treat '*' as ')'. } // If at any point high goes negative, it means too many ')' characters. if (high < 0) return false } // The string is valid if and only if low is 0. low == 0 } }