Valid Parenthesis String

The problem

s contains only the characters "(", ")" and "*". Each star may stand for an opening parenthesis, a closing parenthesis or nothing at all, and you decide for each star separately. Return true if some choice makes the string balanced: every opening parenthesis is closed by a later closing one, and every closing parenthesis closes an earlier opening one. Return false otherwise.

What to write

function solve(s: string): boolean

Input
s = "()"

Output
true

Input
s = "(*)"

Output
true

Constraints

Other characters are parentheses.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Only one kind of parenthesis appears, so it never matters which opening parenthesis a closing one pairs with. Each star has three possible meanings, so a string with many stars can be read in a great many ways: every star triples their number.

2. Hint 2: Ask a smaller question

   Read "(*" from left to right. After the first character one parenthesis is open. After the star, how many could be open? List every possibility. Now add ")" as a third character and list them again.

3. Hint 3: Name the pattern

   You never have to settle what a star means. After each character the number of open parentheses could be anything from a fewest to a most, so carry those two numbers along. One pass, one fixed rule per character, and nothing is tried and taken back: that is a greedy choice. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   After each character, the number of open parentheses can be any whole number from the fewest to the most, and no other. The fewest is never below zero. If the most drops below zero, no way of reading the stars can work.

5. Hint 5: Sketch the pseudocode

   Set fewest = 0 and most = 0. For each character: "(" adds 1 to both, ")" subtracts 1 from both, and a star subtracts 1 from fewest and adds 1 to most. If most is below 0, return false. If fewest is below 0, set it to 0. At the end return true if fewest is 0.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Track the minimum and maximum possible number of unmatched opening parentheses. Reject a negative maximum and finish only if zero remains possible.

The slow way

Try every reading of the stars: each star becomes an opening parenthesis, a closing one, or nothing. Check each resulting string the plain way: a counter goes up for "(" and down for ")", may never drop below zero and must end at zero. This is correct, but each star triples the number of strings. Ten stars give 59,049 strings and twenty give about 3.5 billion.

The insight

You do not need to know what each star means, only how many parentheses could be open. After every character the possible numbers have no gaps: they are all the whole numbers from a fewest to a most, so those two numbers say everything. A star stretches this range at both ends and a parenthesis shifts it. Nothing is ever tried and taken back: a greedy choice.

Step by step

1. Keep the fewest and the most parentheses that could be open. The possible numbers of open parentheses are always all the whole numbers from a lowest to a highest, so those two ends describe them. Before any character both are 0.
2. Update the fewest, counting a star as a closing parenthesis. An opening parenthesis adds one to every possible number and a closing one takes one away. For the low end, a star is read as closing, because that leaves the fewest open.
3. Update the most, counting a star as an opening parenthesis. The high end moves the same way for the two parentheses. A star is read as opening here, because that leaves the most open.
4. If even the most is below zero, a closing parenthesis has no partner. The most counts every star so far as opening. If a closing parenthesis still has nothing to close, no reading of the stars can help, and later characters cannot repair it.
5. The fewest cannot be below zero, so it stops at zero. A number below zero would mean closing a parenthesis that was never opened. Readings that do that are not allowed, and the lowest number an allowed reading can give is zero.
6. The string can be balanced only if the fewest ends at zero. Balanced means nothing is left open at the end. Zero lies in the final range exactly when the low end is zero, because the low end is never below zero.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Keep the fewest and the most parentheses that could be open
  let low = 0,
    high = 0;
  for (const ch of s) {
    // 2. Update the fewest, counting a star as a closing parenthesis
    low += ch === "(" ? 1 : -1;
    // 3. Update the most, counting a star as an opening parenthesis
    high += ch === ")" ? -1 : 1;
    // 4. If even the most is below zero, a closing parenthesis has no partner
    if (high < 0) return false;
    // 5. The fewest cannot be below zero, so it stops at zero
    low = Math.max(0, low);
  }
  // 6. The string can be balanced only if the fewest ends at zero
  return low === 0;
}

function solve(s: string): boolean {
  // 1. Keep the fewest and the most parentheses that could be open
  let low = 0,
    high = 0;
  for (const ch of s) {
    // 2. Update the fewest, counting a star as a closing parenthesis
    low += ch === "(" ? 1 : -1;
    // 3. Update the most, counting a star as an opening parenthesis
    high += ch === ")" ? -1 : 1;
    // 4. If even the most is below zero, a closing parenthesis has no partner
    if (high < 0) return false;
    // 5. The fewest cannot be below zero, so it stops at zero
    low = Math.max(0, low);
  }
  // 6. The string can be balanced only if the fewest ends at zero
  return low === 0;
}

def solve(s):
    # 1. Keep the fewest and the most parentheses that could be open
    low = high = 0
    for char in s:
        # 2. Update the fewest, counting a star as a closing parenthesis
        low += 1 if char == "(" else -1
        # 3. Update the most, counting a star as an opening parenthesis
        high += -1 if char == ")" else 1
        # 4. If even the most is below zero, a closing parenthesis has no partner
        if high < 0:
            return False
        # 5. The fewest cannot be below zero, so it stops at zero
        low = max(0, low)
    # 6. The string can be balanced only if the fewest ends at zero
    return low == 0

Example 2, traced

Input
s = "(*)"

Output
true

Why it works

After every character, the numbers of open parentheses that some allowed reading of the stars can give are exactly the whole numbers from the fewest to the most. A parenthesis shifts that range, a star widens it by one at each end, and numbers below zero are dropped. So some reading balances the string exactly when zero is still in the range at the end.

Time and space

Time O(n), extra space O(1). One pass reads each of the n characters once and changes two numbers, a fixed amount of work, so the time is O(n). Nothing else is stored, however long the string is: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Bring the fewest back to zero when it drops below. Without that, example 2 returns false: the fewest ends at -1, although reading the star as nothing balances the string.
• Test the most after every character. Without that test the string ")" is accepted: the fewest is brought back to zero, and nothing records that a closing parenthesis had no partner.
• Counting the characters without their order is not enough. ")*(" has one opening and one closing parenthesis, but its first character closes nothing, so no reading of the star can balance it.

Pattern

Greedy choice. Builds on Valid Parentheses and Generate Parentheses.

Keep going