678. Jolly parenthesis

678_solution1_stacks.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool checkValidString(char *s) {
  int n = strlen(s);
  // indices of unmatched '(' and '*'
  int *open = malloc((n ? n : 1) * sizeof(int));
  int *star = malloc((n ? n : 1) * sizeof(int));
  int openTop = 0, starTop = 0;
  bool ok = true;

  for (int i = 0; i < n && ok; i++) {
    switch (s[i]) {
    case '(':
      open[openTop++] = i;
      break;
    case '*':
      star[starTop++] = i;
      break;
    case ')':
      if (openTop > 0)
        openTop--;
      else if (starTop > 0)
        starTop--;
      else
        ok = false;
      break;
    }
  }

  // each leftover '(' needs a later '*' to close it
  while (ok && openTop > 0) {
    if (starTop == 0 || star[starTop - 1] < open[openTop - 1])
      ok = false;
    else {
      openTop--;
      starTop--;
    }
  }

  free(open);
  free(star);
  return ok;
}

678_solution2_counters.c

#include <stdbool.h>

// hi is the count if every * is a '('. If even that drops below 0, there's an
// unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
// it to 0 throws away choices that would close more than is open.
bool checkValidString(char *s) {
  int lo = 0, hi = 0; // min and max possible number of open '('

  for (; *s; s++) {
    if (*s == '(') {
      lo++;
      hi++;
    } else if (*s == ')') {
      lo--;
      hi--;
    } else {
      lo--;
      hi++;
    } // '*' could be ')' or '('

    if (hi < 0)
      return false; // too many ')', even with every '*' as '('
    if (lo < 0)
      lo = 0; // the count can't go negative, so drop those choices
  }

  return lo == 0; // some choice of '*' leaves zero open
}

678_solution1_stacks.cpp

#include <stack>
#include <string>

using namespace std;

class Solution {
public:
  bool checkValidString(string s) {
    stack<int> open, star; // indices of unmatched '(' and '*'

    for (int i = 0; i < s.size(); i++) {
      switch (s[i]) {
      case '(':
        open.push(i);
        break;
      case '*':
        star.push(i);
        break;
      case ')':
        if (!open.empty())
          open.pop();
        else if (!star.empty())
          star.pop();
        else
          return false;
        break;
      }
    }

    // each leftover '(' needs a later '*' to close it
    while (!open.empty()) {
      if (star.empty() || star.top() < open.top())
        return false;
      open.pop();
      star.pop();
    }
    return true;
  }
};

678_solution2_counters.cpp

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
  // hi is the count if every * is a '('. If even that drops below 0, there’s an
  // unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
  // it to 0 throws away choices that would close more than is open.
  bool checkValidString(string s) {
    int lo = 0, hi = 0; // min and max possible number of open '('

    for (char c : s) {
      if (c == '(') {
        lo++;
        hi++;
      } else if (c == ')') {
        lo--;
        hi--;
      } else {
        lo--;
        hi++;
      } // '*' could be ')' or '('

      if (hi < 0)
        return false;  // too many ')', even with every '*' as '('
      lo = max(lo, 0); // the count can't go negative, so drop those choices
    }

    return lo == 0; // some choice of '*' leaves zero open
  }
};

678_solution1_stacks.go

package greedy

func checkValidString(s string) bool {
    var open, star []int // indices of unmatched '(' and '*'

    for i := 0; i < len(s); i++ {
        switch s[i] {
        case '(':
            open = append(open, i)
        case '*':
            star = append(star, i)
        case ')':
            if len(open) > 0 {
                open = open[:len(open)-1]
            } else if len(star) > 0 {
                star = star[:len(star)-1]
            } else {
                return false
            }
        }
    }

    // each leftover '(' needs a later '*' to close it
    for len(open) > 0 {
        if len(star) == 0 || star[len(star)-1] < open[len(open)-1] {
            return false
        }
        open = open[:len(open)-1]
        star = star[:len(star)-1]
    }
    return true
}

678_solution2_counters.go

package greedy

// hi is the count if every * is a '('. If even that drops below 0, there's an
// unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
// it to 0 throws away choices that would close more than is open.
func checkValidString(s string) bool {
    lo, hi := 0, 0 // min and max possible number of open '('

    for i := 0; i < len(s); i++ {
        switch s[i] {
        case '(':
            lo++
            hi++
        case ')':
            lo--
            hi--
        default: // '*' could be ')' or '('
            lo--
            hi++
        }

        if hi < 0 {
            return false // too many ')', even with every '*' as '('
        }
        lo = max(lo, 0) // the count can't go negative, so drop those choices
    }

    return lo == 0 // some choice of '*' leaves zero open
}

678_solution1_stacks.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> open = new ArrayDeque<>(), star = new ArrayDeque<>(); // indices of unmatched '(' and '*'

        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '(' -> open.push(i);
                case '*' -> star.push(i);
                case ')' -> {
                    if (!open.isEmpty())
                        open.pop();
                    else if (!star.isEmpty())
                        star.pop();
                    else
                        return false;
                }
            }
        }

        // each leftover '(' needs a later '*' to close it
        while (!open.isEmpty()) {
            if (star.isEmpty() || star.peek() < open.peek())
                return false;
            open.pop();
            star.pop();
        }
        return true;
    }
}

678_solution2_counters.java

class Solution {
    // hi is the count if every * is a '('. If even that drops below 0, there's an
    // unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
    // it to 0 throws away choices that would close more than is open.
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0; // min and max possible number of open '('

        for (char c : s.toCharArray()) {
            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                lo--;
                hi--;
            } else {
                lo--;
                hi++;
            } // '*' could be ')' or '('

            if (hi < 0)
                return false; // too many ')', even with every '*' as '('
            lo = Math.max(lo, 0); // the count can't go negative, so drop those choices
        }

        return lo == 0; // some choice of '*' leaves zero open
    }
}

678_solution1_stacks.js

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function (s) {
  const open = [], star = []; // indices of unmatched '(' and '*'

  for (let i = 0; i < s.length; i++) {
    switch (s[i]) {
      case "(":
        open.push(i);
        break;
      case "*":
        star.push(i);
        break;
      case ")":
        if (open.length) open.pop();
        else if (star.length) star.pop();
        else return false;
        break;
    }
  }

  // each leftover '(' needs a later '*' to close it
  while (open.length) {
    if (!star.length || star[star.length - 1] < open[open.length - 1]) return false;
    open.pop();
    star.pop();
  }
  return true;
};

678_solution2_counters.js

/**
 * hi is the count if every * is a '('. If even that drops below 0, there's an
 * unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
 * it to 0 throws away choices that would close more than is open.
 *
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function (s) {
  let lo = 0, hi = 0; // min and max possible number of open '('

  for (const c of s) {
    if (c === "(") {
      lo++;
      hi++;
    } else if (c === ")") {
      lo--;
      hi--;
    } else {
      lo--;
      hi++;
    } // '*' could be ')' or '('

    if (hi < 0) return false; // too many ')', even with every '*' as '('
    lo = Math.max(lo, 0); // the count can't go negative, so drop those choices
  }

  return lo === 0; // some choice of '*' leaves zero open
};

678_solution1_stacks.py

class Solution:
    def checkValidString(self, s: str) -> bool:
        open_, star = [], []  # indices of unmatched '(' and '*'

        for i, c in enumerate(s):
            if c == "(":
                open_.append(i)
            elif c == "*":
                star.append(i)
            elif open_:
                open_.pop()
            elif star:
                star.pop()
            else:
                return False

        # each leftover '(' needs a later '*' to close it
        while open_:
            if not star or star[-1] < open_[-1]:
                return False
            open_.pop()
            star.pop()
        return True

678_solution2_counters.py

class Solution:
    # hi is the count if every * is a '('. If even that drops below 0, there's an
    # unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
    # it to 0 throws away choices that would close more than is open.
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0  # min and max possible number of open '('

        for c in s:
            if c == "(":
                lo += 1
                hi += 1
            elif c == ")":
                lo -= 1
                hi -= 1
            else:  # '*' could be ')' or '('
                lo -= 1
                hi += 1

            if hi < 0:
                return False  # too many ')', even with every '*' as '('
            lo = max(lo, 0)  # the count can't go negative, so drop those choices

        return lo == 0  # some choice of '*' leaves zero open

678_solution1_stacks.rs

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let (mut open, mut star) = (Vec::new(), Vec::new()); // indices of unmatched '(' and '*'

        for (i, c) in s.bytes().enumerate() {
            match c {
                b'(' => open.push(i),
                b'*' => star.push(i),
                _ => {
                    if open.pop().is_none() && star.pop().is_none() {
                        return false;
                    }
                }
            }
        }

        // each leftover '(' needs a later '*' to close it
        while let Some(o) = open.pop() {
            match star.pop() {
                Some(st) if st > o => {}
                _ => return false,
            }
        }
        true
    }
}

678_solution2_counters.rs

impl Solution {
    // hi is the count if every * is a '('. If even that drops below 0, there's an
    // unmatched ')' no matter what. lo is the count if every * is a ')'. Clamping
    // it to 0 throws away choices that would close more than is open.
    pub fn check_valid_string(s: String) -> bool {
        let (mut lo, mut hi) = (0, 0); // min and max possible number of open '('

        for c in s.bytes() {
            match c {
                b'(' => {
                    lo += 1;
                    hi += 1;
                }
                b')' => {
                    lo -= 1;
                    hi -= 1;
                }
                _ => {
                    // '*' could be ')' or '('
                    lo -= 1;
                    hi += 1;
                }
            }

            if hi < 0 {
                return false; // too many ')', even with every '*' as '('
            }
            lo = lo.max(0); // the count can't go negative, so drop those choices
        }

        lo == 0 // some choice of '*' leaves zero open
    }
}