algoadvance

Leetcode 678. Valid Parenthesis String

Problem Statement

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

The string is considered valid if:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

Clarifying Questions

  1. Q: Can the input string be empty?
    • A: Yes, if the input string is empty, it is considered valid.
  2. Q: What is the maximum length of the string s?
    • A: The length of the string s will be in the range [1, 100].
  3. Q: Can the string contain characters other than ‘(‘, ‘)’ or ‘*’?
    • A: No, the string will only contain the characters ‘(‘, ‘)’ and ‘*’.

Strategy

To determine if the string s is valid, we can use a greedy approach. Here’s a concise plan:

  1. We maintain two counters, low and high, representing the possible range of open parentheses.
  2. As we iterate through the string:
    • If we encounter ‘(‘, we increment both low and high.
    • If we encounter ‘)’, we decrement both low and high.
    • If we encounter ‘*’, we decrement low (considering it as a ‘)’ to keep the minimum open parentheses as small as possible) and increment high (considering it as a ‘(‘ to maximize the possibility).
  3. After iterating through the string, if low is greater than 0, it means there are unmatched open parentheses which cannot be made up by any *. Hence, return false.
  4. If high is non-negative, then it means we managed to balance out the parentheses, thus return true.

This logic ensures that at any point, the number of open parentheses is adjusted keeping the worst scenario in mind using the minimum and maximum bounds (low and high).

Code

public class ValidParenthesisString {
    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                if (low > 0) low--;
                high--;
            } else { // case '*'
                if (low > 0) low--;
                high++;
            }
            if (high < 0) return false; // more ')' than '(' or '*'
        }
        return low == 0;
    }
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the input string s. This is because we process each character in the string exactly once.

The space complexity is O(1) since we only use a fixed amount of extra space regardless of the input size (specifically, we use two integer variables).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI